Một số nguyên dương được gọi là tổng nguyên tố nếu số đó có tổng bình phương các chữ số là một số nguyên tố.

Ví dụ:

• Số 14 là số tổng nguyên tố, vì ~1^2 + 4^2 = 17~ là số nguyên tố.
• Số 682 không phải là số tổng nguyên tố, vì ~6^2 + 8^2 + 2^2 = 104~ không phải là số nguyên tố.

Bình có dãy ~A~ gồm ~N~ số nguyên dương: ~A_1, A_2, …, A_N~ (~N ≤ 10^6~).
Bình muốn biết trong dãy ~A~ có bao nhiêu số là số tổng nguyên tố.

Yêu cầu:
Đếm số lượng các số tổng nguyên tố trong dãy số ~A~.

Input (TNT.INP)

• Dòng 1: chứa số nguyên dương ~N~ là số lượng phần tử của dãy ~A~.
• Dòng 2: chứa ~N~ số nguyên dương ~A_i~ (~0 < A_i < 10^{18}~), các số cách nhau một khoảng trắng.

Output (TNT.OUT)

• Một số nguyên duy nhất: số lượng số tổng nguyên tố tìm được trong dãy ~A~.

Ví dụ

TNT.INP

5
234 98 767 3 502

TNT.OUT

2

Giới hạn

• 64% số test ứng với ~n ≤ 10^5~.
• 36% số test ứng với ~10^5 < n ≤ 10^6~.