Busy Beaver realmente disfruta de los números compuestos. Un día vio un número en una pizarra y quiso convertirlo en compuesto sin cambiarlo demasiado.

Se te da un entero positivo $N$, cuyos dígitos son todos $1$ y $2$.

Elimina como máximo un dígito de $N$, posiblemente dejando a $\boldsymbol{N}$ igual que antes, de modo que $N$ se convierta en un número compuesto. No puedes reordenar los dígitos que no elimines. Para demostrar que tu nuevo número es compuesto, también debes imprimir un factor no trivial.

Un entero positivo $d$ es un factor no trivial de un entero positivo $n$ si $n$ es múltiplo de $d$, $d \neq 1$ y $d \neq n$.

Entrada

La primera línea contiene un entero positivo $T$ ($1 \le T \le 200$), el número de casos de prueba.

Cada caso de prueba contiene una línea: un entero positivo $N$ ($10^3 < N < 10^{200}$) que consiste únicamente en los dígitos $1$ y $2$.

Salida

Para cada caso de prueba, imprime una línea con dos números separados por un espacio.

Primero imprime un entero positivo $M$, tal que $M = N$ o $M$ sea el resultado de eliminar uno de los dígitos de $N$. Luego, imprime un entero positivo $K$ tal que $M$ sea múltiplo de $K$ y $1 < K < M$.

Se puede demostrar que siempre existe una solución bajo las restricciones del problema. Si hay múltiples valores posibles para $M$ y/o $K$, cualquier combinación válida será aceptada.

Subtareas

• ($10$ puntos) Los dígitos de $N$ son todos $2$.
• ($10$ puntos) Los dígitos de $N$ son todos $1$.
• ($10$ puntos) $N < 10^4$.
• ($20$ puntos) $N < 10^8$.
• ($50$ puntos) Sin otras restricciones.

Ejemplos

Entrada 1

4
121212
11121
12211
212221112112211

Salida 1

121212 10101
1121 59
2211 67
21221112112211 4933994911

Nota

En el primer caso de prueba, $121212$ ya es compuesto, por lo que no tenemos que eliminar ningún dígito, y podemos imprimir uno de sus factores no triviales. $10101$ es una posibilidad, ya que $121212 = 12 \cdot 10101$.

En el segundo ejemplo, podemos eliminar el primer $1$ para convertir el número en $1121$, el cual es compuesto ya que $1121 = 19 \cdot 59$, e imprimir $19$ o $59$ funcionaría. También podríamos haber dejado $11121$ tal como está; si hacemos eso, algunas de las posibles respuestas son 11121 33 y 11121 337.

En el tercer ejemplo, $12211$ es primo, por lo que debemos eliminar algún dígito. Otras posibles soluciones son 1211 7 y 1221 37.