Một nhà triết gia lỗi lạc đã từng đặt câu hỏi: "Ligma là gì?".

Ngày nay, Ligma vẫn còn đang là một vấn đề nan giải, nhưng với kỹ thuật khoa học hiện đại của thế kỉ XXI, các nhà khoa học đã tìm ra được một số tính chất đặc trưng của số Ligma.

Số Ligma là số nguyên dương thỏa mãn ít nhất một trong các tính chất sau:

1. Tổng chữ số là một số nguyên tố.
2. Tổng của các chữ số ở vị trí chẵn là một số nguyên tố.
3. Tổng của các chữ số ở vị trí lẻ là một số nguyên tố.

Cho ~Q~ truy vấn, mỗi truy vấn cho một số nguyên dương ~K~, tìm số Ligma bé thứ ~K~.

Ví dụ

• Số ~14~ là một số Ligma (tổng của các chữ số là ~5~, thỏa mãn ~(1)~)
• Số ~69420~ là một số Ligma (tổng của các chữ số ở vị trí chẵn là ~9+2=11~, thỏa mãn ~(2)~)
• Số ~18274~ cũng là một số Ligma (tổng của các chữ số ở vị trí lẻ là ~1 + 2 + 4 = 7~, thỏa mãn ~(3)~)
• Số ~177013, 19, 48~ đều không phải là số Ligma.

Input

• Dòng đầu tiên nhập vào số ~Q~ ~(Q \leq 5 \times 10^5)~.
• ~Q~ dòng tiếp theo, mỗi dòng nhập vào số nguyên dương ~K~ ~(K \leq 10^{15})~.

Outpu

• Gồm ~Q~ dòng, dòng thứ ~i~ là kết quả của truy vấn thứ ~i~.

Sample Input

7
1
2
3
4
5
6
1000000000000000

Sample Output

2
3
5
7
11
12
1822532371972654

Scoring