Recently Watson learned the concept of coprime numbers and now he wonders given an array A1, A2 . . . AN what is the size of the largest subset of the array such that the each pair of elements in the subset is coprime.

Watson asks Sherlock for help and in turn Sherlock needs you.

Input 
First line contains T, the number of test cases. 
Each test case contains N in one line, number of elements in the array.  
Next line contains N space separated elements A1, A2 . . . AN.    

Output 
For each test case, output the required answer in one line.

Constraints: 
1 ≤ T ≤ 10 
25% test data: 1 ≤ N ≤ 10    
75% test data: 1 ≤ N ≤ 50    
1 ≤ Ai ≤ 50      

SAMPLE INPUT
1
5
2 3 2 3 2

SAMPLE OUTPUT
2

Explanation

The largest subset would be taking one of A[0], A[1], A[2] and taking one of A[3], A[4].
def prime(n):
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

primes = [i for i in range(2, 51) if prime(i)]
def f(n):
    ans = 0
    for p in primes:
        if n % p == 0:
            ans += 1
    return ans

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

for _ in range(int(raw_input())):
    n = int(raw_input())
    a = list(map(int, raw_input().split()))

    ans = a.count(1)

    a = set(a)

    if 1 in a:
        a.remove(1)

    a = list(a)
    while len(a) > 0:
        a = sorted(a, key = lambda x: f(x))
        ans += 1
        elem = a[0]

        a = list(filter(lambda x: gcd(x, elem) == 1, a))
    print(ans)