You are given an array a consisting of n integers. You need to find the sum of all the common divisors between the given integers.

For example: suppose the given numbers are 4, 6 and 8. The common divisors between them are 1 and 2. So the answer will be 3.

Input

The first line of the input will contain the number of test cases t (1 <= t <= 10).

For each test case, there will be two lines of input. First line will contain the number of integers in the array n (1 <= n <= 10⁵). The following line will contain the n integers a[1], a[2], a[3] ... a[n] (1 <= a[i] <= 10⁹) where a[i] is the i-th element of the array a.

Output

For every test case print just one integer in a new line, the sum of all the common divisors between the given integers.

Example

Input:
3
3
4 6 8
2
15 13
1
5

Output:
3
1
6