Busy Beaver는 합성수를 정말 좋아합니다. 어느 날 그는 칠판에 적힌 숫자를 보고, 숫자를 크게 바꾸지 않으면서 합성수로 만들고 싶어 했습니다.

모든 자릿수가 $1$과 $2$로만 이루어진 양의 정수 $N$이 주어집니다.

$N$에서 최대 한 개의 자릿수를 삭제하여(삭제하지 않고 $N$을 그대로 두는 것도 가능) $N$이 합성수가 되도록 만드십시오. 삭제하지 않은 자릿수의 순서를 바꿀 수는 없습니다. 새로 만든 수가 합성수임을 증명하기 위해, 그 수의 자명하지 않은(nontrivial) 약수 하나를 함께 출력해야 합니다.

양의 정수 $d$가 양의 정수 $n$의 자명하지 않은 약수라는 것은 $n$이 $d$의 배수이고, $d \neq 1$이며, $d \neq n$임을 의미합니다.

입력

첫 번째 줄에는 테스트 케이스의 개수 $T$ ($1 \le T \le 200$)가 주어집니다.

각 테스트 케이스는 한 줄로 구성되며, $1$과 $2$로만 이루어진 양의 정수 $N$ ($10^3 < N < 10^{200}$)이 주어집니다.

출력

각 테스트 케이스마다 공백으로 구분된 두 수를 출력하십시오.

첫 번째로 $M$을 출력합니다. $M$은 $N$과 같거나 $N$에서 자릿수 하나를 삭제한 수여야 합니다. 그 다음 $M$의 배수이면서 $1 < K < M$을 만족하는 양의 정수 $K$를 출력합니다.

문제의 제한 조건 하에서 항상 해가 존재함이 보장됩니다. $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$는 이미 합성수이므로 자릿수를 삭제할 필요가 없으며, 자명하지 않은 약수 중 하나를 출력할 수 있습니다. $121212 = 12 \cdot 10101$이므로 $10101$은 가능한 답 중 하나입니다.

두 번째 예제에서는 첫 번째 $1$을 삭제하여 $1121$로 만들 수 있습니다. $1121 = 19 \cdot 59$이므로 합성수이며, $19$나 $59$ 중 하나를 출력하면 됩니다. $11121$을 그대로 두는 것도 가능합니다. 그대로 둘 경우 가능한 답으로는 11121 33이나 11121 337 등이 있습니다.

세 번째 예제에서 $12211$은 소수이므로 반드시 자릿수를 하나 삭제해야 합니다. 다른 가능한 해로는 1211 7이나 1221 37 등이 있습니다.