Problem Description
Give nonnegative integers x1…n which are less than 32677, calculate yi,j=xi×xjmod32677. HazelFan wants to know how many sextuples (a,b,c,d,e,f) are there, satisfies gcd(ya,b,yc,d)=gcd(yc,d,ye,f)=gcd(ye,f,ya,b)=1, module 230.
Input
The first line contains a positive integer T(1≤T≤5), denoting the number of test cases.
For each test case:
The first line contains a positive integer n(1≤n≤2×105).
The second line contains n nonnegative integers x1...n(0≤xi<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
