Hệ thống trí tuệ nhân tạo của trung tâm dữ liệu đang phân tích một luồng thông tin khổng lồ. Mỗi gói dữ liệu được gắn một mã số nguyên dương A_i. Để giải mã một gói dữ liệu, hệ thống cần biết số lượng các thừa số nguyên tố tạo thành mã số đó (tính cả các thừa số lặp lại).

Ví dụ: Mã số 12 có 3 thừa số nguyên tố vì 12=2×2×3.

Cho một luồng dữ liệu gồm Q mã số. Hãy tính tổng số lượng thừa số nguyên tố của tất cả Q mã số đó.

Dữ liệu vào (Input):

Dòng đầu tiên chứa số nguyên dương Q — số lượng gói dữ liệu.

Dòng thứ hai chứa Q số nguyên dương A_1,A_2,…,A_Q, các số cách nhau bởi một khoảng trắng.

Dữ liệu ra (Output):

In ra một số nguyên duy nhất là tổng số lượng các thừa số nguyên tố của toàn bộ Q mã số.

Ràng buộc (Constraints):

1≤Q≤10^6

2≤A_i≤10^6

Ví dụ (Example):

Input:

4
12 5 20 17

Output:

8

Giải thích ví dụ:

Mã số 12=2×2×3 → có 3 thừa số.


Mã số 5=5 → có 1 thừa số.

Mã số 20=2×2×5 → có 3 thừa số.

Mã số 17=17 → có 1 thừa số.

Tổng số lượng thừa số là: 3+1+3+1=8.