TÍnh số bộ gồm 4 số mà USCLN của chúng là 1 trong tập N số nguyên cho trước

Input

Dòng đầu là số test case, các dòng tiếp theo, dòng đầu tiền là số N (1<=N <=10000), sau đó là N số nguyên >=1 và <= 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 
Output:
1 
0 
34