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 ~b~ (~b \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ó ~n~ phần tử ~a_1, a_2, ..., a_n~ và hỏi có bao nhiêu số có đúng ~3~ ước số dương trong dãy số ~A~.

Input

• Đọc từ file văn bản Homework.inp gồm hai dòng:
• Dòng 1: Chứa duy nhất số nguyên dương ~n~ (~1 \le n \le 10^4~).
• Dòng 2: Gồm ~n~ số nguyên dương ~a_i~ (~0 < a_i \le 10^9~ với mọi ~1 \le i \le n~), giữa các số cách nhau bởi một dấu cách.

Output

• Ghi ra file văn bản Homework.out 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~.

Ràng buộc

• ~1 \le n \le 10^4~
• ~0 < a_i \le 10^9~ với mọi ~1 \le i \le n~.

Sample Input 1

4
9 8 81 3

Sample Output 1

1

Giải thích: ~n = 4~, chỉ có phần tử ~9~ có đúng ~3~ ước số là ~1~, ~3~ và ~9~.

Sample Input 2

3
10 7 100

Sample Output 2

0