Time Limit: 1.0 s

Memory Limit: 256.0 MB

Description

Lets say \(gcd(Gi)\) means the gcd of a group or combination of any \(i\) elements of the array \(A[]\).

and \(∑gcd(Gi)\) means summation of the gcd of all possible groups of size \(i\).

find \((∑gcd(G1) * ∑gcd(G2) * ∑gcd(G3).....* ∑gcd(Gn))\)

\(gcd(e1,e2,e3...en)\) means the greatest common divisor among all elements \(e1,e2,e3...en\)

since the answer can be too large print it mod 1e9+7

Input

first line of input takes an integer \(T\) : number of testcases
first line of each testcase takes an integer \(N\) : size of the array A[]
second line of each testcase takes \(N\) integers A1,A2...An

\(1 <= T <= 100\)
\(1 <= N <= 10\)
\(1 <= Ai <= 1000\)

Output

for each testcase output 1 integer

Sample

3
1
5
2
2 2
3
2 3 4

5
8
36

in the 2nd testcase :
\(∑gcd(G1) = (2+2) = 4\)
\(∑gcd(G2) = gcd(2,2) = 2\)
\(ans = 4*2 = 8\)

in the 3rd testcase:
\(∑gcd(G1) = (2+3+4) = 9\)
\(∑gcd(G2) = {gcd(2,3)+gcd(2,4)+gcd(3,4)} = (1+2+1) = 4\)
\(∑gcd(G3) = gcd(2,3,4) = 1\)
\(ans = 9*4*1 = 36\)