With the plan to capture Luke and lure him to the Dark Side of the Force, Vader has brought ~n~ followers to Cloud City. Among them are bounty hunters, storm troopers, and imperial officers. The ~i~-th follower has a capability of ~a_i~. To carry out this complex mission, Vader will divide the ~n~ followers into one or more groups. He will calculate the effectiveness of a division as follows:

• Let ~k~ be the number of groups, and calculate the capability ~s_i~ of group ~i~ by summing the capabilities of all members in that group.

• The effectiveness of the division is calculated as ~\gcd(s_1, s_2, \dots, s_k).~

Vader wants to calculate the total effectiveness across all divisions. Two divisions are considered different if there exist two followers in the same group in one division but in different groups in the other division.

Input

The first line contains a positive integer ~n~ (~1 \leq n \leq 16~), the number of followers Vader has brought.

The second line contains ~n~ positive integers ~a_1, a_2, \dots, a_n~ (~1 \leq a_i \leq 100~), describing the capabilities of the followers that Vader has brought.

Output

Print a single line with the sum of effectiveness across all divisions.

Sample Input 1

4
1 2 3 4

Sample Output 1

32

Sample Input 2

6
1 2 4 8 16 32

Sample Output 2

357