Limits
1s, 512 MB

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 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)**

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

Input | Output |
---|---|

4 2 3 3 4 | 2 5 5 9 |

Input | Output |
---|---|

4 2 3 4 5 | 2 5 9 14 |