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$, которое либо равно $N$, либо получено из $N$ удалением одной цифры. Затем выведите целое положительное число $K$ такое, что $M$ делится на $K$ и $1 < K < M$.

Можно доказать, что решение всегда существует при заданных ограничениях. Если существует несколько возможных значений $M$ и/или $K$, любая допустимая комбинация будет принята.

Подзадачи

• ($10$ баллов) Все цифры $N$ — двойки.
• ($10$ баллов) Все цифры $N$ — единицы.
• ($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.