You are given an array of size \(N\). Rearrange it in such a manner that the sum of the GCD over all the non-empty prefixes of the array is maximum.

GCD here means greatest common divisior. It is the largest number which divides any set of numbers without leaving any remainder with any of them.

Input format:

• The first line contains a single integer \(N\).
• The second line, contains \(N\) space-separated integers, the array elements. 

Output format:

Print the answer — the maximum possible sum of all the prefix GCD's of the rearranged array.

Constraints:

\(1 \leq N \leq 20 \\ 1 \leq A_i \leq 10^9 \\ \)