Trong buổi học Toán tiếp theo, Thầy lại cho ôn tập về số học, trong đó có các khái niệm: ước số, số chính phương, số nguyên tố, … và cho bài tập về nhà cho cả lớp tự luyện tập.

Khái niệm:

• Số chính phương là số tự nhiên có căn bậc hai là một số tự nhiên, hay nói cách khác, số chính phương bằng bình phương (lũy thừa bậc $2$) của một số nguyên.

• Số nguyên $𝑏$ $(𝑏\ne 0)$ gọi là ước số của số nguyên $a$, nếu $a$ chia hết cho $b$.

• Số nguyên tố là số tự nhiên chỉ có $2$ ước số, gồm $1$ và chính nó.

Yêu cầu: Bài tập về nhà Thầy cho dãy số $A$ có $𝑛$ phần tử ${𝑎}_1,{𝑎}_2,\dots ,{𝑎}_{𝑛}$ và hỏi có bao nhiêu số có đúng $3$ ước số dương trong dãy số $A$.

Input

Dòng 1: Chứa duy nhất số nguyên dương $𝑛$ $(1\le 𝑛\le {10}^4)$.

Dòng 2: Gồm $n$ số nguyên dương ${𝑎}_{𝑖}$ $(0<{𝑎}_{𝑖}\le {10}^9:\forall 1\le 𝑖\le 𝑛)$, giữa các số cách nhau bởi một dấu cách.

Output

Gồm duy nhất số nguyên dương là số lượng số có đúng $3$ ước số dương. Nếu không có số nào thỏa mãn thì ghi $0$.

Sample Input 1

4
3 9 8 81

Sample Output 1

1

Giải thích: $n=4$, chỉ có phần tử ${𝑎}_2=9:$ có $3$ ước số là $1,3,9$.

Sample Input 2

3
10 7 100

Sample Output 2

0

Ràng buộc:

• $1\le n\le {10}^4;0<a_i\le {10}^9:\forall 1\le i\le n$.