Lưu ý: Bạn có thể nhấn vào biểu tượng hình quả cầu và chuyển sang tiếng Anh để đọc đề bài này bằng tiếng Anh.

Bạn nhặt được \(19\$\) trên đường cùng với một mảnh giấy nhỏ ghi như sau:

“Hãy tìm số nguyên tố nhỏ nhất, lớn hơn \(N\) mà tổng các chữ số của số nguyên tố đó là một hợp số”.

Input

• Dòng đầu ghi \(Q\) không quá \(10\) - số câu hỏi.
• \(Q\) dòng tiếp theo, mỗi dòng ghi số nguyên dương \(N\) không quá \(10^{16}\).

Output

• Ứng với mỗi câu hỏi, in ra đáp án cần tìm.

Example

1
16

17