J. Shift the Number
time limit per test
2 s
memory limit per test
512 megabytes
input
standard input
output
standard output

Monocarp invented a new operation on integers: $$$n \rightarrow x$$$, which he calls a cyclic shift. The operation is defined only for positive integers $$$n$$$ that do not contain zeros in their decimal representation, and for positive integers $$$x$$$. It is defined as follows: let the decimal representation of $$$n$$$ be $$$\overline{n_1 n_2 \dots n_{m-1} n_m}$$$, then:

$$$$$$n \rightarrow x = \begin{cases} \overline{n_m n_1 n_2 \dots n_{m - 1}}, & \text{if } x = 1 \\ (n \rightarrow (x - 1)) \rightarrow 1, & \text{otherwise} \end{cases} $$$$$$

In other words, $$$n \rightarrow x$$$ is the integer you get if you perform the following operation $$$x$$$ times: move the rightmost digit in the decimal representation of $$$n$$$ to the leftmost position, shifting all other digits one position to the right.

For example, $$$123 \rightarrow 1 = 312$$$, $$$123 \rightarrow 2 = 231$$$, $$$123 \rightarrow 9 = 123$$$, $$$1 \rightarrow 1 = 1$$$.

Monocarp is interested in how similar this operation is to addition. Given an integer $$$n$$$, he wants to find all values of $$$x$$$ such that $$$n \rightarrow x = n + x$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

The only line of each test case contains an integer $$$n$$$ ($$$1 \le n \lt 10^9$$$).

Additional constraint on the input: all digits in the decimal representation of $$$n$$$ are not equal to $$$0$$$.

Output

For each test case, print the number of suitable values of $$$x$$$. Then, print these values of $$$x$$$ in increasing order.

Example
Input
7
12
34
228
1113
1114
12345678
123456789
Output
1
9
1
9
0

1
198
2
27 2997
7
11111103 22222134 33332445 44435556 55466667 65777778 68888889
0