You have n different numbers and you have to make all of them same by performing two operations.
Operation 1 : Pick a group of numbers and make them equal to any number which divides all of the numbers in that group but make sure you cant make the numbers equal to 1
Operation 2 : Pick a number and make it equal to 1
Find out minimum operations required to make all numbers equal.
Input
First line contains t which is the total number of test cases. First line of the test case contains an integer N as input. Next line contains N integers.
Output
You have to provide minimum number of operations to make all the elements of array equal
Constraints
\(1\le N \le10^5\)
\(1\le A[i] \le10^6\)
\(1\le t \le10\)