Busy Beaver rất thích các hợp số. Một ngày nọ, chú nhìn thấy một số trên bảng và muốn biến nó thành hợp số mà không làm thay đổi quá nhiều.

Bạn được cho một số nguyên dương $N$, trong đó tất cả các chữ số đều là $1$ hoặc $2$.

Hãy xóa nhiều nhất một chữ số từ $N$, có thể giữ nguyên $N$ như ban đầu, sao cho $N$ trở thành hợp số. Bạn không được phép thay đổi thứ tự các chữ số còn lại. Để chứng minh số mới của bạn là hợp số, bạn cũng cần xuất ra một ước số không tầm thường của nó.

Một số nguyên dương $d$ được gọi là ước số không tầm thường của số nguyên dương $n$ nếu $n$ là bội số của $d$, $d \neq 1$ và $d \neq n$.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên dương $T$ ($1 \le T \le 200$), số lượng bộ dữ liệu.

Mỗi bộ dữ liệu chứa một dòng: một số nguyên dương $N$ ($10^3 < N < 10^{200}$) chỉ bao gồm các chữ số $1$ và $2$.

Dữ liệu ra

Với mỗi bộ dữ liệu, hãy xuất ra một dòng gồm hai số cách nhau bởi một khoảng trắng.

Đầu tiên, xuất ra một số nguyên dương $M$, sao cho $M = N$ hoặc $M$ là số thu được sau khi xóa một chữ số của $N$. Sau đó, xuất ra một số nguyên dương $K$ sao cho $M$ là bội số của $K$ và $1 < K < M$.

Có thể chứng minh rằng luôn tồn tại một lời giải thỏa mãn các ràng buộc của bài toán. Nếu có nhiều giá trị $M$ và/hoặc $K$ khả thi, bất kỳ tổ hợp hợp lệ nào cũng sẽ được chấp nhận.

Nhiệm vụ con

• ($10$ điểm) Tất cả các chữ số của $N$ đều là $2$.
• ($10$ điểm) Tất cả các chữ số của $N$ đều là $1$.
• ($10$ điểm) $N < 10^4$.
• ($20$ điểm) $N < 10^8$.
• ($50$ điểm) Không có ràng buộc nào khác.

Ví dụ

Ví dụ 1

4
121212
11121
12211
212221112112211

Kết quả 1

121212 10101
1121 59
2211 67
21221112112211 4933994911

Ghi chú

Trong bộ dữ liệu ví dụ đầu tiên, $121212$ đã là một hợp số, vì vậy chúng ta không cần xóa chữ số nào và có thể xuất ra một trong các ước số không tầm thường của nó. $10101$ là một khả năng, vì $121212 = 12 \cdot 10101$.

Trong ví dụ thứ hai, chúng ta có thể xóa chữ số $1$ đầu tiên để biến số đó thành $1121$, đây là một hợp số vì $1121 = 19 \cdot 59$, và việc xuất ra $19$ hoặc $59$ đều hợp lệ. Chúng ta cũng có thể giữ nguyên $11121$; nếu làm vậy, một số câu trả lời khả thi là 11121 33 và 11121 337.

Trong ví dụ thứ ba, $12211$ là số nguyên tố, vì vậy chúng ta bắt buộc phải xóa một chữ số. Một số lời giải khả thi khác là 1211 7 và 1221 37.