You are given an array A consisting of N integers.
Find the number of [subsequences] S having length M such that:

M > 1;
For any pair of indices (i,j) in the subsequence S, (lcm(M, S_{i}) - S_{i}) = (lcm(M, S_{j}) - S_{j}). Here lcm(a,b) denotes the [lcm] of integers a and b.

Since the answer can be huge, print it modulo 10^{9}+7.

Note that, a subsequence of an array is obtained by deleting the elements at some (possibly none or all) indices of the array. For example, all the subsequences of array [1, 2, 2] are {[A_{1}], [A_{2}], [A_{3}], [A_{1}, A_{2}], [A_{1}, A_{3}], [A_{2}, A_{3}], [A_{1}, A_{2}, A_{3}] }, that is, {[1], [2], [2], [1, 2], [1, 2], [2, 2], [1, 2, 2] }.

------ Input Format ------

• The first line of input contains T, the number of test cases.
• The first line of each test case contains an integer N, the number of elements in the array.
• The next line of each test case contains $N integers A_{1}, A_{2}, \ldots, A_{N}$, the elements of the array A.

------ Output Format ------

For each test case, output a single integer denoting the answer modulo 10^{9} + 7.

------ Constraints ------

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{7}$
- Sum of $N$ of over all test cases does not exceed $10^{5}$.

----- Sample Input 1 ------
3
3
1 2 3
3
2 2 2
5
2 2 3 3 3
----- Sample Output 1 ------
0
4
5
----- explanation 1 ------
- Test case $1$: There is no subsequence satisfying all the conditions.

• Test case $2$: The valid subsequences are: $\{A_{1}, A_{2}\}, \{A_{1}, A_{3}\}, \{A_{2}, A_{3}\},$ and $\{A_{1}, A_{2}, A_{3}\}.$
  For subsequence $\{A_{1}, A_{3}\}$, $(lcm(2, A_{1}) - A_{1}) = (lcm(2, A_{3}) - A_{3}) = 0$.
  Similarly, for all pairs in the subsequence $\{A_{1}, A_{2}, A_{3}\}$, $(lcm(3, S_{i}) -S_{i}) = (lcm(3, S_{j}) - S_{j}) = 4$.

• Test case $3$: The valid subsequences are: $\{A_{1}, A_{2}\}, \{A_{3}, A_{4}\}, \{A_{4}, A_{5}\}, \{A_{3}, A_{5}\},$ and $\{A_{3}, A_{4}, A_{5}\}.$
  For subsequence $\{A_{1}, A_{2}\}$, $(lcm(2, A_{1}) - A_{1}) = (lcm(2, A_{2}) - A_{2})$. Same condition holds for subsequences $\{A_{3}, A_{4}\}, \{A_{4}, A_{5}\}, \{A_{3}, A_{5}\}$.
  For all pairs in the subsequence $\{A_{3}, A_{4}, A_{5}\}$, $(lcm(3, S_{i}) -S_{i}) = (lcm(3, S_{j}) - S_{j}) = 0$.

见题面

见题面