Math is Fun

Problem Description

A funny boy, XYZ introduced a simple math function called GLL for a set of integers$S=\{a_1,a_2,\cdots ,a_n \}$:

Here,$GCD(S) = GCD(a_1,a_2,\cdots ,a_n)$ means the greatest common divisor of integers $a_1,a_2,\cdots ,a_n$;$LCM(S) = LCM(a_1,a_2,\cdots ,a_n)$ means the least common multiple of integers $a_1,a_2,\cdots ,a_n$ For the singleton set, GCD and LCM will be the number only. For example, GCD of $S = \{x\}$ , will be $x$ only. Consider the LCM and GCD of an empty set as $0$ . Now, he is interested in finding the sum of GLL values of all subsets for a given set $A$ , but he finds the problem very hard. Help him calculate the following:

As the answer can be very large, print it modulo 1000000009(10^9 + 9).

Input

The first line contains T, the number of test cases. T test cases follow. The first line of each test case contains N, the number of elements in $A$ ; the next line contains N space-separated positive integers. $1 \leq T \leq 50$ $1 \leq N \leq 100$ Numbers in the array are in the range [1, 1000]

Output

For each test case, output the answer in a newline.

Sample Input

2
2
2 3
3
2 4 10

Sample Output

71
2904

Hint

Test Case #1: Subset 1: {2} ==> lcm = 2, gcd = 2, gll = 8 Subset 2: {3} ==> lcm = 3, gcd = 3, gll = 27 Subset 3: {2, 3} ==> lcm = 6, gcd = 1, gll = 36 Answer = 8 + 27 + 36 = 71 Test Case #2: Subset 1: {2} ==> lcm = 2, gcd = 2, gll = 8 Subset 2: {4} ==> lcm = 4, gcd = 4, gll = 64 Subset 3: {10} ==> lcm = 10, gcd = 10, gll = 1000 Subset 4: {2, 4} ==> lcm = 4, gcd = 2, gll = 32 Subset 5: {4, 10} ==> lcm = 20, gcd = 2, gll = 800 Subset 6: {2, 10} ==> lcm = 10, gcd = 2, gll = 200 Subset 7: {2, 4, 10} ==> lcm = 20, gcd = 2, gll = 800 Answer = 8 + 64 + 1000 + 32 + 800 + 200 + 800 = 2904

Author

金策工业综合大学（DPRK）

Source

2016 Multi-University Training Contest 9