Cho dãy số \(A\) gồm \(n\) phần tử nguyên dương \(A_1,A_2,…,A_n\). 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ử.

Input

• Đọ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\ (A_i≤10^6)\).

Output

• 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ử.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N≤10^4\) và \(A_i≤3\).
• Subtask \(2\) (\(30\%\) số điểm): \(N≤10^4\) và \(A_i≤8\).
• Subtask \(3\) (\(30\%\) số điểm): \(N≤10^4\) và \(A_i≤10^6\).
• Subtask \(4\) (\(10\%\) số điểm): trường hợp còn lại.

Example

4
1 2 4 10 

3