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.