Bảo hỏi Đức: Số ~11~ và số ~12~ có điểm chung gì liên quan đến số nguyên tố? Sau khi suy nghĩ, Đức nhận ra các số trên có chung đặc điểm là tổng bình phương các chữ số của chúng là một số nguyên tố.

Cụ thể, phân tích số ~11~ ta thấy ~1^2 + 1^2 = 2~, số ~2~ là một số nguyên tố; phân tích số ~12~ ta thấy ~1^2 + 2^2 = 5~, số ~5~ là một số nguyên tố. Hai bạn đặt tên cho các số nguyên dương có tính chất này gọi là số thú vị.

Yêu cầu: Cho số nguyên dương ~n~, hãy tìm số thú vị nhỏ nhất lớn hơn ~n~.

Input

Vào từ file văn bản INTP.INP:

• Dòng đầu tiên chứa số nguyên dương ~T~ là số bộ dữ liệu vào của bài toán (~T \le 10^5~);
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~n~ (~n \le 10^6~).

Output

Ghi ra file văn bản INTP.OUT gồm ~T~ dòng, mỗi dòng ghi một số nguyên dương tương ứng là kết quả tính được theo dữ liệu vào.

Ví dụ

Input

3
9
11
2358

Output

11
12
2362

Giới hạn

• ~1 \le T \le 10^5~, ~1 \le n \le 10^6~.
• Có 40% số test ứng với 40% số điểm thỏa mãn ~T = 1~ và ~n \le 10^3~;
• Có 40% số test ứng với 40% số điểm thỏa mãn ~T \le 10^3~ và ~n \le 10^3~;
• 20% số test còn lại ứng với 20% số điểm không có ràng buộc gì thêm.