Final Sum Reduction

In this problem, you are given $T$ test cases. For each test case, you have an integer $N$ and a list of $N$ integers. Your task is to compute the sum of the integers modulo $10^9+9$. This operation is interpreted as performing exactly $N-1$ reductions until a single integer remains, which is equivalent to computing the sum modulo $10^9+9$. For example, if the given list is [1,2,3], the final result is $1+2+3=6$.

inputFormat

The input begins with an integer $T$, the number of test cases. For each test case, the first line contains an integer $N$. The second line contains $N$ space-separated integers.

outputFormat

For each test case, output a single line containing the final sum of the integers modulo $10^9+9$.## sample

1
3
1 2 3

6