Arrayman

Arrayman is a very famous person. He has an array of n integers. He wants to divide it in a number of subarrays. The cost to create a subarray is the sum of the unique numbers in that subarray. He has to spend sum of unique numbers in each subarray for this. For example: If the array is (2,4,4,6) and he decides to divide like this: {2}, {4,4,6} then total cost will be 2+4+6=12 Taka. But if he divides like this: {2,4},{4,6} then total cost will be 2+4+4+6=16 Taka. Arrayman can divide the array in any number of possible subarrays he wishes (he also can leave the array as it is). But he has to follow one condition. GCD of each subarray must be greater than 1. For example {2,4,6} can be a subarray. But he can't take {2,4,3} as it's gcd is 1. In this problem, you need to find the minimum amount of money Arrayman has to spend.

Input

Input starts with integer n (1<=n<=10^5). Next line contains n space separated integers . ith of them contains a1, a2, ..., an (2<=ai<=10^6)

Output

Print n lines. ith line contains an integer denoting the answer if we consider first i elements of the array

Samples

4
2 3 3 4

2
5
5
9

4
2 3 4 5

2
5
9
14