You are given a set numbers. Output the number of pairs of relatively prime numbers found in the set.

Input

The first line consists of an integer t, the number of test cases. (1 <= t <= 100).

For each test case:

The first line contains the size of the set, N (1 < N <= 100).

The next line contains N space separated integers each of which is in the range [1, 100].

Output

For each test case, output the number of pairs of relatively prime numbers found in the set.

Example

Input:
2
5
1 2 3 4 5 
2
1 1

Output:
9
1