It's the night before Christmas and bitter old Ebenezer Scrooge is sitting grumpily in his manor when he hears a knock at his door.
It is two men seeking donations to provide food and clothing for the poor.
Ebenezer Scrooge laughs in their face and turns them away,
they won't be getting any of his fortune today.
How big was his fortune exactly?
Ebenezer Scrooge decides to spend the holiday counting his money,
amused by those less fortunate, he finds it very funny.

Can you help determine Ebenezer Scrooge's net income? Ebenezer Scrooge retrieves his accounting journal but finds that all the transactions are messed up! His accountant will be receiving a very unpleasant call tomorrow on Christmas day. He finds that the quantities of all the money he has received is always a prime integer and that the amount recorded is that number multiplied by one or more even bigger prime numbers. Ebenezer Scrooge's net income is the lowest prime factor of all the recorded values added up.

Input Specification

The first line contains ~n~ ~(1 \le n \le 10^6)~ representing the number of transactions that increase his account balance.
The next ~n~ lines contain ~n_i~ ~(2 \le n_i \le 10^6)~ representing the quantity recorded for each transaction.
The actual amount received is the lowest prime factor of ~n_i~. Ebenezer Scrooge's net income is the sum of these ~n~ prime factors.
Solutions in Java are encouraged to use fast input reading.

Output Specification

Print Ebenezer Scrooge's net income.

Subtasks

Subtask 1

For 3 points, ~(1 \le n \le 1000)~.

Subtask 2

For 2 additinal points, ~(1 \le n \le 10^5)~.

Subtask 3

For the last 2 points, no additional constraints.

Sample Input

5
49
24
143
667
4

Sample Output

45