5856：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.