You are given an array of positive integers. Define its value as the number of index pairs such that 1\le i<j\le n and \gcd(a_i,a_j)>1.
Find the maximum number of elements that can be removed so that the array's value decreases by at most .
You may remove all elements. The value of an empty array is .
The first line contains one integer (1\le t\le10^5) — the number of test cases.
The first line of each test case contains one integer (1\le n\le2\cdot10^5) — the array length.
The second line contains integers a_1,a_2,\ldots,a_n (1\le a_i\le3\cdot10^5).
The sum of over all test cases does not exceed 2\cdot10^5.
For each test case, print one integer — the maximum number of elements that can be removed.
Example 1
Example 2
Example 3
In the first test case of the first example, the array is [10,2,10,3,7,5,25]. You can remove and : neither belongs to a pair whose greatest common divisor is greater than . It is impossible to remove more than two elements.
In the second test case of the first example, all numbers are pairwise coprime, so the entire array can be removed.
In the first test case of the second example, both sixes can be removed: the value decreases from to . In the second test case, you can remove the number . In the third test case, removing any element eliminates two qualifying pairs, so the answer is .
Subtask ( points): t\le10, n\le20.
Subtask ( points): n\le100, \sum n\le2000.
Subtask ( points): n\le1000, \sum n\le20000.
Subtask ( points): all a_i are prime.
Subtask ( points): no additional constraints.