Math is Fun

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

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:
$$Answer = \sum_{S\subset A}GLL(S)$$

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

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]

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

2
2
2 3
3
2 4 10

71
2904

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

金策工业综合大学（DPRK）

2016 Multi-University Training Contest 9