Challenge From Mr. Professor

One Day Mr. Professor was taking His schedule class on Discrete Mathematics. In this lecture, He was talking about set theory.
Alice was very lazy and Inattentive in this class. Mr. Professor notices him and thinks How to punish him.
After finishing His class Mr. Professor Write Two Function on the blackboard and some description.

g(k) = sum of all subsets from a given set which has cardinality k.
F(S) = ∑g(d); where d is a divisor of the cardinality of the set S.

Example if S ={1,2,3,4}; Here cardinality of S is |S| = 4

F(S) = g(1) + g(2) + g(4);
g(1) = {1} + {2} + {3} + {4} = 1 + 2 + 3 + 4 = 10
g(2) = {1,2} + {1,3} + {1,4} + {2,3} + {2,4}+{3,4} = 3 + 4 + 5 + 5 + 6 + 7 = 30
g(4) = {1,2,3,4} = 10
F(S) = 10 + 30+ 10 = 50

Mr. Professor gives the task to Alice and to write a bug-free c++ or c code to solve the problem for a given set.
You know Alice is a good problem solver, so he asks Mr. Professor about the Constraints of the problem.

Then Mr. professor add Three more lines on the board,

1 <= |S| <= 106
-109 <= Si <= 109 , Si ∈ S\

As the value of F(S) will very Big so print only F(S) mod 999999937

Input

The first line contains an integer T, number of test case.
The second line contains an integer N, size of the set S.
Next line contains N integers, elements of the set Si.

1≤ T ≤ 10
1 <= N, |S| <= 106
-109 ≤ Si ≤ 109, Si ∈ S

Output

For each test case, print a single line containing one integer ― the value of F(S) mod 999999937.

Sample

1
4
1 2 3 4

50