Cho dãy số A gồm n phần tử nguyên dương A1, A2,..., An. Mỗi phần tử có giá trị không vượt quá 10^6 và n < 10^5. Hãy loại một phần tử bất kỳ trong dãy số và đặt P tích các số còn lại. Phân tích thừa số nguyên tố của P, sau đó tính tổng các số mũ trong thừa số nguyên tố đó. Hãy tìm cách bỏ loại bỏ số nào để tổng các số mũ nhỏ nhất có thể.

Ví dụ: cho dãy số gồm 4 số 1;2;4;10. Có 2 cách bỏ đều cho tổng số mũ bằng 3 là nhỏ nhất:

• Cách 1: Loại bỏ số 4, ta có P=1∗2∗10=20=2^2∗5 có tổng số mũ bẳng 3
• Cách 2: Loại bỏ số 10, ta có P=1∗2∗4=8=2^3 có tổng số mũ bẳng 3

Yêu cầu

Cho dãy số A, hãy in ra tổng số mũ nhỏ nhất của phân tích thừa số sau khi bỏ một phần tử.

Dữ liệu vào: Đọc từ file văn bản TSNT.INP:

• Dòng đầu tiên chứa dãy số n (n ≤ 10^5).
• Dòng thứ 2 chứa n phần tử của dãy số A (Ai ≤ 10^6).

Dữ liệu ra: Ghi ra file văn bản TSNT.OUT một số nguyên là tổng số mũ nhỏ nhất của phân tích thừa số sau khi bỏ một phần tử.

Ví dụ

Sample input

4
1 2 4 10

Sample output

3