Busy Beaver bardzo lubi liczby złożone. Pewnego dnia zobaczył liczbę na tablicy i zapragnął uczynić ją złożoną, nie zmieniając jej zbyt mocno.

Dana jest liczba całkowita dodatnia $N$, której wszystkie cyfry to $1$ lub $2$.

Usuń co najwyżej jedną cyfrę z $N$ (możesz również pozostawić $N$ bez zmian), tak aby $N$ stało się liczbą złożoną. Nie wolno zmieniać kolejności cyfr, które nie zostały usunięte. Aby udowodnić, że nowa liczba jest złożona, musisz również wypisać jej nietrywialny dzielnik.

Liczba całkowita dodatnia $d$ jest nietrywialnym dzielnikiem liczby całkowitej dodatniej $n$, jeśli $n$ jest wielokrotnością $d$, $d \neq 1$ oraz $d \neq n$.

Wejście

Pierwsza linia zawiera liczbę całkowitą dodatnią $T$ ($1 \le T \le 200$), liczbę zestawów danych.

Każdy zestaw danych zawiera jedną linię: liczbę całkowitą dodatnią $N$ ($10^3 < N < 10^{200}$) składającą się wyłącznie z cyfr $1$ i $2$.

Wyjście

Dla każdego zestawu danych wypisz w jednej linii dwie liczby oddzielone spacją.

Najpierw wypisz liczbę całkowitą dodatnią $M$, taką że $M = N$ lub $M$ powstaje przez usunięcie jednej cyfry z $N$. Następnie wypisz liczbę całkowitą dodatnią $K$, taką że $M$ jest wielokrotnością $K$ oraz $1 < K < M$.

Można wykazać, że przy podanych ograniczeniach rozwiązanie zawsze istnieje. Jeśli istnieje wiele możliwych wartości $M$ i/lub $K$, każda poprawna kombinacja zostanie zaakceptowana.

Podzadania

• ($10$ punktów) Wszystkie cyfry $N$ to $2$.
• ($10$ punktów) Wszystkie cyfry $N$ to $1$.
• ($10$ punktów) $N < 10^4$.
• ($20$ punktów) $N < 10^8$.
• ($50$ punktów) Brak dodatkowych ograniczeń.

Przykład

Wejście 1

4
121212
11121
12211
212221112112211

Wyjście 1

121212 10101
1121 59
2211 67
21221112112211 4933994911

Uwagi

W pierwszym przypadku testowym liczba $121212$ jest już złożona, więc nie musimy usuwać żadnej cyfry i możemy wypisać jeden z jej nietrywialnych dzielników. $10101$ jest jedną z możliwości, ponieważ $121212 = 12 \cdot 10101$.

W drugim przypadku możemy usunąć pierwszą cyfrę $1$, aby otrzymać liczbę $1121$, która jest złożona, ponieważ $1121 = 19 \cdot 59$. Wypisanie $19$ lub $59$ byłoby poprawne. Można było również pozostawić $11121$ bez zmian; w takim przypadku przykładowymi poprawnymi odpowiedziami byłyby 11121 33 lub 11121 337.

W trzecim przypadku $12211$ jest liczbą pierwszą, więc musimy usunąć jedną cyfrę. Inne możliwe rozwiązania to 1211 7 oraz 1221 37.