Bình là một học sinh yêu môn toán học và cũng rất hứng thú với môn tin học. Bình rất thích thú với chương trình của một cậu bạn học bên lớp chuyên tin khi chỉ cần bấm tổ hợp phím CTRL+ F9 đã có ngay hàng ngàn số nguyên tố.

Bình nghĩ ra bài toán sau: Cho một dãy ~n~ số nguyên dương ~a_1, a_2,..., a_n~.

Đểm số lượng các số ~a_i~, mà ~a_i!~ (~a_i~ giai thừa, ~a_i! = 1 \times 2 \times 3... \times a_i~) chia hết cho ~a_i^2~. Bình loay hoay mãi mà vẫn chưa lập trình xong.

Yêu cầu

Bạn hãy giúp Bình lập chương trình giải bài toán trên.

Input

Dòng đầu số ~n~ ~(1 ≤ n ≤ 100)~

Dòng tiếp theo ghi ~n~ số nguyên dương ~a_1, a_2,..., a_n~ ~(1 ≤ ai ≤ 10^9)~

Output

Số nguyên duy nhất là số lượng các số trong dãy có tính chất đã nêu

Sample Test

Input

5
10 2 4 7 6

Output

2

Giải thích

Chỉ có 2 số ~10~ và ~6~ có thỏa mãn: ~10!~ Chia hết cho ~100~ và ~6!~ Chia hết cho ~36~.