Điểm: 250 Thời gian: 1.0s Bộ nhớ: 488M Input: bàn phím Output: màn hình

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

Test 1

Input
1
16
Output
17

Bình luận