Let there be a K-dimensional Hyperrectangle, where each dimension has a length of n₁,n₂,...n_k.
Each of the Hyperrectangle's unit cells is addressed at (i,j,k,...) and has a value which is equivalent to GCD(i,j,k,...) where 1 <= i <= n₁ , 1 <= j <= n₂ ....

The goal is to sum all the GCD(i,j,k,...) cell values and print the result modulo 10^9 + 7. Note that indexing is from 1 to N and not 0 to N-1.

Input Format
The first line contains an integer T. T testcases follow.
Each testcase contains 2 lines, the first line being K (K-dimension) and the second line contains K space separated integers indicating the size of each dimension - n₁ n₂ n₃ ... n_k

Output Format
Print the sum of all the hyperrectangle cell's GCD values modulo 10^9 + 7 in each line corresponding to each test case.

Constraints
1 <= T <= 1000
2 <= K <= 500
1 <= n_k <= 100000

Sample Input #00

2
2
4 4
2
3 3

Sample Output #00

24
12

Sample Input #01

1
3
3 3 3

Sample Output #01

30

Explanation #00
For the first test case, it's a 4X4 2-dimension Rectangle. The (i,j) address and GCD values of each element at (i,j) will look like

1,1 1,2 1,3 1,4              1 1 1 1  
2,1 2,2 2,3 2,4  => GCD(i,j) 1 2 1 2  
3,1 3,2 3,3 3,4              1 1 3 1  
4,1 4,2 4,3 4,4              1 2 1 4  

Sum of these values is 24

Explanation #00
Similarly for 3X3 GCD (i,j) would look like

1,1 1,2 1,3               1 1 1  
2,1 2,2 2,3  => GCD(i,j)  1 2 1  
3,1 3,2 3,3               1 1 3  

Sum is 12

Explanation #01
Here we have a 3-dimensional 3X3X3 Hyperrectangle or a cube. We can write it's GCD (i,j,k) values in 3 layers.

1,1,1 1,1,2 1,1,3  |  2,1,1 2,1,2 2,1,3  |  3,1,1 3,1,2 3,1,3  
1,2,1 1,2,2 1,2,3  |  2,2,1 2,2,2 2,2,3  |  3,2,1 3,2,2 3,2,3  
1,3,1 1,3,2 1,3,3  |  2,3,1 2,3,2 2,3,3  |  3,3,1 3,3,2 3,3,3  
GCD (i,j,k)
1 1 1              |  1 1 1              |  1 1 1  
1 1 1              |  1 2 1              |  1 1 1  
1 1 1              |  1 1 1              |  1 1 3  

Total Sum = 30

Timelimits Timelimits for this challenge is given here