Busy Beaver really likes composite numbers. One day he saw a number on a blackboard and wanted to make it composite without changing it too much.

You are given a positive integer $N$, whose digits are all $1$'s and $2$'s.

Delete at most one digit from $N$, possibly leaving $\boldsymbol{N}$ the same as before, so that $N$ becomes composite. You cannot reorder digits you do not delete. To prove that your new number is composite, you also need to output a nontrivial factor.

A positive integer $d$ is a nontrivial factor of a positive integer $n$ if $n$ is a multiple of $d$, $d \neq 1$, and $d \neq n$.

Input

The first line contains a positive integer $T$ ($1 \le T \le 200$), the number of test cases.

Each test case contains one line: a positive integer $N$ ($10^3 < N < 10^{200}$) consisting of only the digits $1$ and $2$.

Output

For each test case, output a line with two numbers separated by a space.

First output a positive integer $M$, such that either $M = N$ or $M$ is missing one of the digits of $N$. Then output a positive integer $K$ such that $M$ is a multiple of $K$ and $1 < K < M$.

It can be shown that a solution always exists under the problem's constraints. If there are multiple possible values for $M$ and/or $K$, any valid combination will be accepted.

Scoring

• ($10$ points) $N$'s digits are all $2$'s.
• ($10$ points) $N$'s digits are all $1$'s.
• ($10$ points) $N < 10^4$.
• ($20$ points) $N < 10^8$.
• ($50$ points) No other constraints.

Examples

Input 1

4
121212
11121
12211
212221112112211

Output 1

121212 10101
1121 59
2211 67
21221112112211 4933994911

Note

In the first sample test case, $121212$ is already composite, so we don't have to delete any digit, and we can output one of its nontrivial factors. $10101$ is one possibility, since $121212 = 12 \cdot 10101$.

In the second sample, we can delete the first $1$ to turn the number into $1121$, which is composite since $1121 = 19 \cdot 59$, and outputting either $19$ or $59$ would work. We could also have left $11121$ as it is; if we do that, some of the possible answers are 11121 33 and 11121 337.

In the third sample, $12211$ is prime, so we must delete some digit. Some other possible solutions are 1211 7 and 1221 37.