E. Easy Math Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Kanari recently worked on perfect numbers.

Perfect numbers are a special kind of natural numbers. A number is a perfect number if and only if the sum of all the true factors (divisors other than itself) is equal to itself. Such as $$$6=1+2+3$$$, $$$28=1+2+4+7+14$$$, etc.

Kanari made a kind of semi-perfect number of his own according to the definition of perfect number.

Let $$$S$$$ be the set of all the true factors of the natural number $$$X$$$. If there is a subset of $$$S$$$ such that the sum of the numbers in the subset is equal to the number itself, the number is said to be semi-perfect.

Obviously, all perfect numbers are semiperfect numbers. In addition, there are some numbers that are not perfect, and they also belong to Kanari's semi-perfect numbers. For example, the true factors set of $$$24$$$ is $$$\{1,2,3,4,6,8,12\}$$$, we can select a subset $$$\{2,4,6,12\}$$$, meet that $$$24=2+4+6+12$$$. So $$$24$$$ can be called a semi-perfect number.

Kanari wants to know if he can find an integer $$$k$$$ which is a multiple of positive integer $$$p$$$, such that $$$k$$$ is a semi-perfect number.

Since Kanari is not good at math, he wants the $$$k$$$ not to be too large ($$$k\leq 2\times 10^{18}$$$), and the size of the subset is not larger than 1000. He wants you to give the subset you select.

Input

This problem contains multiple test cases.

The first line contains a single integer $$$T$$$ ($$$1\leq T\leq 4000$$$) indicating the number of test cases.

Then $$$T$$$ cases follow, each of which contains a single interger $$$p$$$ ($$$1\leq p\leq 10^9$$$).

Output

Output $$$2T$$$ lines.

For each test case, if there is some integer $$$k$$$ that satisfy the condition, output two space-separated integers on the first line, $$$k$$$ ($$$k\leq 2\times 10^{18}$$$) and $$$n$$$ ($$$1 \leq n \leq 1000$$$) (the size of the subset you select). Then output $$$n$$$ space-separated integers on the second line, the subset you select.

If you cannot find such $$$k$$$, output -1 on the first line, and an empty line on the second line.

Please don't output extra space at the end of each line.

Example
Input
2
6
1
Output
48 5
2 4 6 12 24
12 4
1 2 3 6