Có một một số được gọi là số đẹp nếu như tổng bình phương chữ số của nó là số nguyên tố. Không chỉ có một số mà có rất nhiều số có tính chất như vậy và nó tạo thành một dãy số đẹp. Để thách thức bạn, vietminh123 đố bạn tìm được số đẹp thứ ~k~ của dãy số đẹp trên (dãy số đẹp được đánh số theo thứ tự tăng dần của các giá trị và bắt đầu từ vị trí ~0~). Không chỉ một mà vietminh123 cho bạn ~t~ câu đố như vậy. Để chứng minh bản thân bạn đã chấp nhận lời thách thức ấy.

Ví dụ, số ~23~ là số đẹp vì ~2^2 + 3^2 = 13~ là số nguyên tố.

Input

• Dòng đầu tiên chứa số nguyên ~t~ ~(1 \le t \le 10^{4})~ là số lượng câu đố của vietminh123 dành cho bạn.
• Dòng tiếp theo chứa một số nguyên ~k~ ~(0 \le k \le 4 \times 10^{6})~ - giá trị thứ ~k~ của dãy bạn cần tìm.

Output

• Với mỗi câu đố thứ ~t_i~ hãy in ra câu trả lời của bạn.

Sample Input 1

3
0
1
2

Sample Output 1

11
12
14