Số T-Prime là số nguyên dương có đúng 3 ước số nguyên dương khác nhau. Ví dụ 49 là số T-Prime vì 49 có đúng 3 ước số nguyên dương là 1, 7, 49.

Yêu cầu: Cho trước số nguyên dương ~N~ (~0 < N ≤ 10^6~) và dãy gồm ~N~ số nguyên dương ~a_1, a_2,...a_N~ (~0 \le a_i \le 10^{10}~).Hãy đếm xem có bao nhiêu số T-Prime trong dãy.

Dữ liệu vào:

• Dòng thứ nhất: Ghi số nguyên ~N~.
• Dòng 2: Ghi ~N~ số nguyên ~a_1, a_2,...a_N~

Dữ liệu ra:

• Một số nguyên duy nhất là kết quả của bài toán.

Ví dụ:

Input

8
3 4 5 9 36 49 55 121

Output

4