Busy Beaver 非常喜歡合數。有一天，他在黑板上看到一個數字，想要在不更動太多的情況下將其變為合數。

給你一個正整數 $N$，其位數皆為 $1$ 或 $2$。

請刪除 $N$ 中的 至多一個位數（也可以 保持 $N$ 不變），使得 $N$ 變為合數。你不能重新排列未刪除的位數。為了證明你得到的新數字是合數，你還需要輸出一個非平凡因數。

若正整數 $d$ 為正整數 $n$ 的非平凡因數，則 $n$ 必須是 $d$ 的倍數，且 $d \neq 1$ 且 $d \neq n$。

輸入格式

第一行包含一個正整數 $T$ ($1 \le T \le 200$)，代表測試資料的組數。

每個測試資料包含一行：一個正整數 $N$ ($10^3 < N < 10^{200}$)，僅由數字 $1$ 和 $2$ 組成。

輸出格式

對於每組測試資料，輸出一行包含兩個以空格分隔的數字。

首先輸出一個正整數 $M$，使得 $M = N$ 或 $M$ 為刪除 $N$ 中其中一個位數後的結果。接著輸出一個正整數 $K$，使得 $M$ 為 $K$ 的倍數且 $1 < K < M$。

可以證明在題目限制下，解一定存在。若存在多種可能的 $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$ 本身即為合數，因此我們不需要刪除任何位數，並可以輸出其非平凡因數之一。$10101$ 是一種可能，因為 $121212 = 12 \cdot 10101$。

在第二個範例中，我們可以刪除第一個 $1$ 將數字變為 $1121$，它是合數，因為 $1121 = 19 \cdot 59$，輸出 $19$ 或 $59$ 皆可。我們也可以保持 $11121$ 不變；若這樣做，可能的答案包括 11121 33 和 11121 337。

在第三個範例中，$12211$ 是質數，因此我們必須刪除某個位數。其他可能的解包括 1211 7 和 1221 37。