Let there be a K-dimensional Hyperrectangle, where each dimension has a length of n1,n2,...nk.
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 <= n1 , 1 <= j <= n2 ....
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.
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 -
n1 n2 n3 ... nk
Print the sum of all the hyperrectangle cell's GCD values modulo 10^9 + 7 in each line corresponding to each test case.
1 <= T <= 1000
2 <= K <= 500
1 <= nk <= 100000
Sample Input #00
Sample Output #00
Sample Input #01
3 3 3
Sample Output #01
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