Read problems statements in Mandarin Chinese and Russian.

Roma gave Chef an array of intergers.

Chef wants to make all integers in the array equal to 1.

In a single operation, he can select a prime number p and a subset of the integers, and then divide all of the integers in the subset by p.

Chef can make this operation only if every integer in the selected subset is divisible by p.

Please help Chef to make all the integers in the array equal to 1 with minimum number of operations.

------ Input ------

The first line of input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the length of the array that Roma gave Chef.
The second line contains N space-separated integers A_{1}, A_{2}, ..., A_{N} denoting the integers in the array.

------ Output ------

For each test case, output a single line containing one integer - the minimum number of operations needed to make all numbers equal to 1.

------ Constraints ------

$Subtask 1 (10 points): T = 5, 1 ≤ N ≤ 10^{5}, 1 ≤ A_{i} ≤ 3$
$Subtask 2 (40 points): T = 3, 1 ≤ N ≤ 10, 1 ≤ A_{i} ≤ 10^{6}$
$Subtask 3 (50 points): T = 3, 1 ≤ N ≤ 10^{5}, 1 ≤ A_{i} ≤ 10^{6}$

----- Sample Input 1 ------
1
3
1 2 4
----- Sample Output 1 ------
2

见题面

见题面