Số đẹp

Số đẹp là số nguyên tố mà khi ta xóa đi một số tuỳ ý các chữ số bên phải của số đó thì phần còn lại vẫn tạo thành một số nguyên tố.

Ví dụ:

• Số 7331 là một số đẹp có 4 chữ số vì 7331, 733, 73, 7 đều là các số nguyên tố.
• Số 5 là một số đẹp có 1 chữ số vì số 5 là số nguyên tố.

Cho dãy $A$ gồm $N$ số nguyên dương: $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^{15}$).

Yêu cầu: Hãy liệt kê tất cả các số đẹp có trong dãy trên.

Dữ liệu vào từ file văn bản SODEP.INP:

• Dòng 1: Ghi số nguyên dương $N$ ($1 \le N \le 1000$).
• Dòng 2: Ghi $N$ số nguyên dương của dãy $A$. Các số được ghi cách nhau một dấu cách.

Dữ liệu ra file văn bản SODEP.OUT:

• Gồm nhiều dòng, mỗi dòng ghi một số đẹp tìm được.
• Nếu không tìm được số đẹp trong dãy thì ghi ra file một số: 0.

• Có 70% số test ứng với 70% số điểm của bài có $A_i < 10^5$.
• Có 30% số test ứng với 30% số điểm của bài có $10^5 \le A_i \le 10^{15}$.