Recently Watson learned the concept of coprime numbers and now he wonders given an array A₁, A₂ . . . A_N 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 A₁, A₂ . . . A_N.

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 ≤ A_i ≤ 50