A foundry casts n ingots, each starting with a positive integer mass. Call an ingot a reference ingot for a prime p if its starting mass is exactly p. For any ingot i, its current mass may be divided by a prime p, repeatedly, as long as it stays evenly divisible by p, provided at least one other ingot j (j != i) is a reference ingot for p; that reference role depends only on ingot j's starting mass, so it is permanent and unaffected by anything later done to ingot j itself (including reducing ingot j's own mass through other operations). An ingot can never use its own starting mass as its own reference — some other ingot must supply it, even when the two masses happen to coincide. These division operations may be applied to any ingot, using any eligible reference prime, any number of times, in any order. Find the minimum possible sum of all n ingots' masses achievable this way.

Input format

The first line contains an integer n. The second line contains n space-separated integers, the starting masses of the ingots.

Output format

Print a single integer: the minimum achievable total mass of all ingots.

Constraints

• 1 <= n <= 2000
• 1 <= mass_i <= 1000000

4
18 2 2 25

36

3
9 3 3

3