All Kill

Time Limit: 8000/4000 MS (Java/Others)

Memory Limit: 524288/524288 K (Java/Others)

Description

Give nonnegative integers $x_{1…n}$ which are less than $32677$, calculate $y_{i,j}=x_i\times x_j\mod32677$. HazelFan wants to know how many sextuples $(a,b,c,d,e,f)$ are there, satisfies $\gcd(y_{a,b},y_{c,d})=\gcd(y_{c,d},y_{e,f})=\gcd(y_{e,f},y_{a,b})=1$, module $2^{30}$.

Input

The first line contains a positive integer $T(1\leq T\leq5)$, denoting the number of test cases.
For each test case:
The first line contains a positive integer $n(1\leq n\leq2\times10^5)$.
The second line contains $n$ nonnegative integers $x_{1...n}(0\leq x_i<32677)$.

Output

For each test case:
A single line contains a nonnegative integer, denoting the answer.

Sample Input

2 1 1 5 1 2 3 4 5

Sample Output

1 1087

Hint

liuyiding

Source

2017 Multi-University Training Contest - Te

提交代码