J. Air Taxi Game
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

It's common knowledge that Corviknight fly air taxis in Galar. However, since they are always on edge due to the presence of Tinkaton, they think about interesting number theory properties to occupy their minds.

One day, Rowlet proposed a simple and fun game to the Corviknight population. It is known that Galar has $$$N$$$ cities, and each has a unique population $$$a_i$$$. Rowlet wants to find the number of ordered triples of cities $$$(i, j, k)$$$ such that the greatest common divisor of the populations of the first two cities is equal to the least common multiple of the populations of the second two cities.

Input

The first line of input contains a number $$$T$$$ $$$(1 \leq T \leq 5*10^4)$$$, denoting the number of test cases.

Each test case contains on its first line $$$N$$$ $$$(1 \leq N \leq 2*10^5)$$$, the number of cities in Galar. The second line contains $$$N$$$ integers $$$a_i$$$ $$$(1 \leq a_i \leq 2*10^5)$$$. All values are pairwise distinct.

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

Output

A single number, the number of triples.

Example
Input
4
3
1 2 4
4
1 6 2 3
6
1 3 4 8 6 24
5
1 7 2 5 3
Output
1
2
8
0
Note

In the first test case, the only valid triple is $$$(3, 2, 1)$$$, since $$$gcd(a_3, a_2) = lcm(a_2, a_1)$$$.

In the second test case, the valid triples are $$$(2, 3, 1)$$$ and $$$(2, 4, 1)$$$.

In the last test case, it can be shown that there are no valid triples.