"B, your old friends are no longer in Beijing. Why are you still here?"

"Probably because of some accidents; otherwise, this problem wouldn't be called 'Shelter'."

"Hmm, where will you go after this?"

"To a place without winter."

For a positive integer $n$, we define $p = F(n, b)$ as the product of its digits in base $b$.

For example, $F(3338, 10) = 216$.

Consider the following problem: given $p$ and $b$, find the smallest $n$ such that $p = F(n, b)$.

This is a very interesting problem. For some $b$, we can use a greedy approach. For example, if $b=10$ and $p=216$:

We can perform trial division from $b-1$ down to $2$ until $p$ becomes $1$. The answer is $389$. It can be verified that $389$ is the smallest $n$ satisfying $p = F(n, b)$.

However, for some bases $b$, the greedy approach does not work. For example, $b = 9$ and $p = 216$. The greedy approach yields $3338$, while the optimal solution is $666$ (both in base $9$).

This problem asks you to provide such a counterexample for a given base $b$, or to indicate that no such counterexample exists.

Due to limited computational resources, the product of all digits in the counterexample must not exceed $10^{18}$. If the product of all digits in the smallest counterexample exceeds $10^{18}$, you should output $-1$.

Input

Read data from standard input.

The first line contains an integer $t$, representing the number of test cases.

Each of the following lines contains an integer $b$, representing the base.

Output

Output to standard output.

If no counterexample exists, output a single integer $-1$ on a line.

If a counterexample exists, first output an integer $k$, representing the number of digits of the counterexample $n$, followed by $k$ decimal integers on the same line, representing the digits of any optimal counterexample.

Examples

Input 1

3
8
9
10

Output 1

-1
3 6 6 6
-1

Note

Don't be nervous, you'll be fine.

Constraints

For the 1st test case, the score is $30$, $1 \leq n \leq 32$;

For the 2nd test case, the score is $40$, $1 \leq n \leq 100$;

For the 3rd test case, the score is $30$, $1 \leq t \leq 200, 1 \leq n \leq 100000$.