H. Divide And Multiply
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Once upon a time, Attal was playing with an array and applying some operations on it. But during his playing, he noticed that he hates the array if it's elements are not the same.

Attal was a lazy man. So he gives Yaman the array $$$a$$$ that contains $$$n$$$ integers $$$[a_1, a_2, ... a_n]$$$, and he asks Yaman to make their elements equal using two kinds of operations:

  1. Choose an integer $$$i$$$ such that $$$1 \le i \le n$$$ and an integer number $$$k$$$, and replace $$$a_i$$$ with $$$k * a_i$$$.
  2. Choose an integer $$$i$$$ such that $$$1 \le i \le n$$$ and an integer number $$$k$$$ that divides $$$a_i$$$ and replace $$$a_i $$$ with $$$\frac{a_i}{k}$$$.

Note that the number $$$k$$$ can be different in each operation.

Yaman wants to make the array's elements equal using the minimum number of operations (possibly zero). Help Yaman to find it.

Input

The first line contains the number of test cases $$$t$$$ $$$( 1 \le t \le 10^{5} )$$$. A description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ $$$( 1 \le n \le 10^{6} )$$$, — the length of the array $$$a$$$.

The next line contains $$$n$$$ integers $$$a_i$$$ $$$( 1 \le a_i \le n)$$$, — the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^{6}$$$.

Output

Print the minimum number of operations needed to make the elements of the array $$$a$$$ equal.

Example
Input
3
3
1 2 3
4
1 2 2 4
3
3 3 3
Output
2
2
0