Cho dãy ~A~ độ dài ~N~, đếm số bộ ~(i, j, k, z)~ thỏa mãn ~1 \leq i < j < k < z \leq N~ và ~gcd(A_i, A_j, A_k, A_z) = 1~

Trong đó hàm ~gcd(x_1, x_2, .., x_k)~ trả về ~UCLN~ của ~k~ số ~x_1, x_2, .., x_k~

Input

Dòng đầu là số test case, các dòng tiếp theo, dòng đầu tiền là số ~N~ ~(1 \le N \le 10000)~, sau đó là ~N~ số nguyên ~> = 1~ và ~\le 10000~.

Output

In ra số cần tính cho mỗi bộ test.

Sample Input

4
2 3 4 5
4
2 4 6 8
7
2 3 4 5 7 6 8

Sample Output

1
0
34