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 ~𝑏~ ~(𝑏 ≠ 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, … , 𝑎_𝑛~ 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 ≤ 𝑛 ≤ 10^4)~.

Dòng 2: Gồm ~n~ số nguyên dương ~𝑎_𝑖~ ~(0 < 𝑎_𝑖 ≤ 10^9: ∀1 ≤ 𝑖 ≤ 𝑛)~, 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 ≤ n ≤ 10^4; 0 < a_i ≤ 10^9:∀1 ≤ i ≤ n~.