Description

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

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

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

This problem is quite interesting. For some bases $b$, we can solve it greedily. For example, if $b = 10, p = 216$, we can try dividing $p$ by integers from $b - 1$ down to $2$ until $p$ becomes $1$. The answer is $389$, and you can verify that $389$ is the smallest $n$ satisfying $p = F(n, b)$.

However, for some bases $b$, this greedy approach does not work. For instance, when $b = 9, p = 216$, the greedy solution is $3338$, while the optimal answer is $666$ (both in base $9$).

In this problem, for a given base $b$, either produce such a counterexample or state that no such counterexample exists.

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

Input Format

Read from standard input.

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

Each of the next $t$ lines contains an integer $b$, the base.

Output Format

Output to standard output.

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

If a counterexample exists, first output an integer $k$, the number of digits of $n$ in the counterexample. Then, on the same line, output $k$ decimal integers, which represent any optimal solution (the digits of the smallest $n$ for that counterexample) in base $b$.

3
8
9
10

-1
3 6 6 6
-1

Hint

• For the 1st subtask (30 points), $1 \leq b \leq 32$.
• For the 2nd subtask (40 points), $1 \leq b \leq 100$.
• For the 3rd subtask (30 points), $1 \leq t \leq 200, 1 \leq b \leq 100000$.

Translated by ChatGPT 5