Busy Beaver aime beaucoup les nombres composés. Un jour, il a vu un nombre sur un tableau noir et a voulu le rendre composé sans trop le modifier.

On vous donne un entier positif $N$, dont les chiffres sont tous des $1$ et des $2$.

Supprimez au plus un chiffre de $N$, en laissant éventuellement $N$ inchangé, de sorte que $N$ devienne composé. Vous ne pouvez pas réorganiser les chiffres que vous ne supprimez pas. Pour prouver que votre nouveau nombre est composé, vous devez également afficher un facteur non trivial.

Un entier positif $d$ est un facteur non trivial d'un entier positif $n$ si $n$ est un multiple de $d$, $d \neq 1$ et $d \neq n$.

Entrée

La première ligne contient un entier positif $T$ ($1 \le T \le 200$), le nombre de cas de test.

Chaque cas de test contient une ligne : un entier positif $N$ ($10^3 < N < 10^{200}$) composé uniquement des chiffres $1$ et $2$.

Sortie

Pour chaque cas de test, affichez une ligne avec deux nombres séparés par un espace.

Affichez d'abord un entier positif $M$, tel que soit $M = N$, soit $M$ est le résultat de la suppression d'un des chiffres de $N$. Ensuite, affichez un entier positif $K$ tel que $M$ soit un multiple de $K$ et $1 < K < M$.

Il peut être démontré qu'une solution existe toujours sous les contraintes du problème. S'il existe plusieurs valeurs possibles pour $M$ et/ou $K$, toute combinaison valide sera acceptée.

Sous-tâches

• ($10$ points) Les chiffres de $N$ sont tous des $2$.
• ($10$ points) Les chiffres de $N$ sont tous des $1$.
• ($10$ points) $N < 10^4$.
• ($20$ points) $N < 10^8$.
• ($50$ points) Aucune autre contrainte.

Exemples

Entrée 1

4
121212
11121
12211
212221112112211

Sortie 1

121212 10101
1121 59
2211 67
21221112112211 4933994911

Remarque

Dans le premier cas de test, $121212$ est déjà composé, nous n'avons donc pas besoin de supprimer de chiffre, et nous pouvons afficher l'un de ses facteurs non triviaux. $10101$ est une possibilité, puisque $121212 = 12 \cdot 10101$.

Dans le deuxième exemple, nous pouvons supprimer le premier $1$ pour transformer le nombre en $1121$, qui est composé puisque $1121 = 19 \cdot 59$, et afficher soit $19$, soit $59$ fonctionnerait. Nous aurions également pu laisser $11121$ tel quel ; si nous le faisons, certaines des réponses possibles sont 11121 33 et 11121 337.

Dans le troisième exemple, $12211$ est premier, nous devons donc supprimer un chiffre. D'autres solutions possibles sont 1211 7 et 1221 37.