C. Delete One Digit
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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 \lt N \lt 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 \lt K \lt 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 \lt 10^4$$$.
  • ($$$20$$$ points) $$$N \lt 10^8$$$.
  • ($$$50$$$ points) No other constraints.
Example
Input
4
121212
11121
12211
212221112112211
Output
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.