Question
Luigi and Uniformity
Luigi has an array A of N positive integers. He wants to make all elements of the array equal.
In one move, he can
- Choose an index i (1 ≤ i ≤ N) and divide the element Ai by any one of its divisors. In other words, he can choose a positive integer X such that X | Ai and set Ai = Ai / X.
Find the minimum number of moves required to make all the elements of the array equal.
Input
The first line of input will contain a single integer T, denoting the number of test cases.
Each test case consists of two lines of input.
The first line of each test case contains N, the size of array A.
The second line of each test case contains N space-separated integers, the elements of array A.
Constraints
1 ≤ T ≤ 1000
1 ≤ N ≤ 3000
1 ≤ Ai ≤ 109
Each test case consists of two lines of input.
The first line of each test case contains N, the size of array A.
The second line of each test case contains N space-separated integers, the elements of array A.
Constraints
1 ≤ T ≤ 1000
1 ≤ N ≤ 3000
1 ≤ Ai ≤ 109
Output
For each test case, output on a new line, the minimum number of moves required to make all elements of the array equal.
Example
Input
2
2
11 22
5
38 38 38 38 38
Output
1
0
Explanation
Test case 1: We can change 22 to 11 using an operation (divide by 2). Thus, using one operation, we made all the elements equal.
Test case 2: All numbers are already same. Thus, we do not need to do any operations.
2
2
11 22
5
38 38 38 38 38
Output
1
0
Explanation
Test case 1: We can change 22 to 11 using an operation (divide by 2). Thus, using one operation, we made all the elements equal.
Test case 2: All numbers are already same. Thus, we do not need to do any operations.