F. GCD <-> LCM
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array of integers $$$a_1, a_2, \ldots, a_n$$$.

A quadruple $$$(i, j, k, l)$$$ is called good if:

  • $$$1 \le i, j, k, l \le n$$$,
  • all indices are pairwise distinct, and
  • $$$\gcd(a_i, a_j) = \operatorname{lcm}(a_k, a_l)$$$.

Your task is to count the number of ordered good quadruples.

Since the answer can be large, print it modulo $$$10^9 + 7$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.

Each test case consists of two lines:

  • The first line contains an integer $$$n$$$ ($$$4 \le n \le 10^5$$$).
  • The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, output a single integer — the number of ordered good quadruples modulo $$$10^9 + 7$$$.

Example
Input
2
4
4 3 1 1
6
2 2 2 2 3 5
Output
4
24
Note

In the first test case, the good quadruples of indices are: (1, 2, 3, 4), (1, 2, 4, 3), (2, 1, 3, 4), (2, 1, 4, 3) since $$$\gcd(4,3) = 1$$$ and $$$\operatorname{lcm}(1,1) = 1$$$.