Trong thế giới Arcadia, mỗi viên tinh thể năng lượng được đánh số bằng một số nguyên dương. Các nhà khoa học phát hiện rằng chỉ những viên mang năng lượng thuần khiết mới có thể kích hoạt cổng dịch chuyển.

Một số được gọi là số tốt nếu đồng thời thỏa mãn:

• Nó là số chính phương.
• Căn bậc hai của nó là một số nguyên tố.

Ví dụ:

• 49 là số tốt vì: ~49=7^2~ và 7 là số nguyên tố.

• 36 không phải số tốt vì: ~36=6^2~ nhưng 6 không phải số nguyên tố.

Bạn được cung cấp một dãy gồm N số nguyên dương. Hãy đếm xem trong dãy có bao nhiêu số tốt.

Dữ liệu vào

• Dòng đầu chứa số nguyên N — số lượng phần tử trong dãy.
• Dòng thứ hai chứa N số nguyên dương ~a_i~.

~1 \le N \le 10^5~

~1 \le a_i \le 10^9~

Dữ liệu ra

In ra một số nguyên duy nhất — số lượng số tốt xuất hiện trong dãy.

Ví dụ 1

Input

5
4 9 16 25 49

Output

4

Giải thích

Các số tốt là:

• ~4 = 2²~
• ~9 = 3²~
• ~25 = 5²~
• ~49 = 7²~

Trong khi:

• ~16 = 4²~ nhưng 4 không phải số nguyên tố.

Ví dụ 2

Input

6
1 8 10 27 36 121

Output

1