THỰC HÀNH

Một số nguyên dương được gọi là số nửa nguyên tố nếu nó chỉ có đúng 3 ước nguyên dương.

Bạn được cho một dãy gồm N số nguyên dương phân biệt a₁, a₂, …, a_N, hãy đếm xem trong dãy số đó có bao nhiêu số nửa nguyên tố.

Dữ liệu vào:

• Dòng đầu chứa số nguyên dương N.
• Dòng thứ hai chứa N số nguyên dương a₁, a₂, …, a_N, mỗi số cách nhau một khoảng trống.

Dữ liệu ra:

Một số nguyên duy nhất là số lượng số nửa nguyên tố trong dãy đã cho.

Ví dụ:

Dữ liệu vào:
5
1 3 4 6 8

Dữ liệu ra:
1

Giải thích: Trong ví dụ trên: số 4 có 3 ước nguyên dương là 1, 2, 4.

Giới hạn:

• 40% số test (ứng với 40% số điểm của bài) 1 ≤ N ≤ 100, 1 ≤ a_i ≤ 10⁴.
• 40% số test (ứng với 40% số điểm của bài) 1 ≤ N ≤ 1000, 1 ≤ a_i ≤ 10⁶.
• 20% số test (ứng với 20% số điểm của bài) 1 ≤ N ≤ 10⁵, 1 ≤ a_i ≤ 10¹².