Busy Beaver は合成数が大好きです。ある日、彼は黒板に書かれた数を見て、それをあまり変えずに合成数にしたいと考えました。

すべての桁が $1$ または $2$ である正の整数 $N$ が与えられます。

$N$ から 最大で $1$ 桁 を削除して（何も削除しなくてもよい）、$N$ を合成数にしてください。削除しなかった桁の順序を変更することはできません。新しい数が合成数であることを証明するために、その数の自明でない約数も出力してください。

正の整数 $d$ が正の整数 $n$ の自明でない約数であるとは、$n$ が $d$ の倍数であり、かつ $d \neq 1$ かつ $d \neq n$ であることを指します。

入力

最初の行には、テストケースの数 $T$ ($1 \le T \le 200$) が含まれます。

各テストケースは $1$ 行で構成され、数字 $1$ と $2$ のみからなる正の整数 $N$ ($10^3 < N < 10^{200}$) が与えられます。

出力

各テストケースについて、スペースで区切られた $2$ つの数を出力してください。

まず、$M = N$ であるか、または $N$ から $1$ 桁削除して得られる正の整数 $M$ を出力します。次に、$M$ の倍数であり、$1 < K < M$ を満たす正の整数 $K$ を出力します。

問題の制約下で常に解が存在することが示せます。$M$ や $K$ に複数の可能な値がある場合、どの有効な組み合わせでも正解となります。

小課題

• ($10$ 点) $N$ のすべての桁が $2$ である。
• ($10$ 点) $N$ のすべての桁が $1$ である。
• ($10$ 点) $N < 10^4$。
• ($20$ 点) $N < 10^8$。
• ($50$ 点) その他の制約はない。

入出力例

入力 1

4
121212
11121
12211
212221112112211

出力 1

121212 10101
1121 59
2211 67
21221112112211 4933994911

注記

最初のサンプルケースでは、$121212$ はすでに合成数であるため、桁を削除する必要はなく、その自明でない約数のいずれかを出力できます。$121212 = 12 \cdot 10101$ であるため、$10101$ はその可能性の一つです。

2番目のサンプルでは、最初の $1$ を削除して $1121$ にすることで合成数にできます。$1121 = 19 \cdot 59$ なので、$19$ または $59$ を出力すれば正解となります。また、$11121$ をそのままにすることも可能です。その場合、11121 33 や 11121 337 なども答えとして考えられます。

3番目のサンプルでは、$12211$ は素数であるため、いずれかの桁を削除しなければなりません。他の可能な解として 1211 7 や 1221 37 などがあります。