Leonhard Euler（1707–1783）是一位伟大的数学家。在本题中，我们将讨论一个以他命名的函数，即欧拉函数 φ。

对于自然数 $n$，欧拉函数 φ 的值是满足 $1 \le k \le n$ 且与 $n$ 互质的数 $k$ 的个数。两数互质是指它们没有大于 1 的公因数。例如，φ(6) = 2，因为 1 和 5 与 6 互质，而 2、3、4 和 6 则不是。

如果欧拉还活着，他可能会提出如下问题：给定一个自然数 $n$，找出所有满足方程 φ(x) = n 的自然数 $x$。

输入格式

输入的第一行包含一个自然数 $t$（$1 \le t \le 5$），表示数据组的数量。接下来的 $t$ 行每行描述一个数据组。每个描述包含一个自然数 $n$（$1 \le n \le 10^{10}$）。

输出格式

你的程序应依次输出每个数据组的答案。每个答案包含两行。第一行应输出解的个数。第二行应按升序输出所有满足方程的解。如果方程无解，则该数据组的第二行应留空。

示例

输入

4
8
10
13
6

输出

5
15 16 20 24 30
2
11 22
0

4
7 9 14 18