A prime number is an integer greater than $$$1$$$, which has exactly two divisors. For example, $$$7$$$ is a prime, since it has two divisors $$$\{1, 7\}$$$. A composite number is an integer greater than $$$1$$$, which has more than two different divisors.

Note that the integer $$$1$$$ is neither prime nor composite.

Let's look at some composite number $$$v$$$. It has several divisors: some divisors are prime, others are composite themselves. If the number of prime divisors of $$$v$$$ is less or equal to the number of composite divisors, let's name $$$v$$$ as strongly composite.

For example, number $$$12$$$ has $$$6$$$ divisors: $$$\{1, 2, 3, 4, 6, 12\}$$$, two divisors $$$2$$$ and $$$3$$$ are prime, while three divisors $$$4$$$, $$$6$$$ and $$$12$$$ are composite. So, $$$12$$$ is strongly composite. Other examples of strongly composite numbers are $$$4$$$, $$$8$$$, $$$9$$$, $$$16$$$ and so on.

On the other side, divisors of $$$15$$$ are $$$\{1, 3, 5, 15\}$$$: $$$3$$$ and $$$5$$$ are prime, $$$15$$$ is composite. So, $$$15$$$ is not a strongly composite. Other examples are: $$$2$$$, $$$3$$$, $$$5$$$, $$$6$$$, $$$7$$$, $$$10$$$ and so on.

You are given $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$a_i \gt 1$$$). You have to build an array $$$b_1, b_2, \dots, b_k$$$ such that following conditions are satisfied:

Product of all elements of array $$$a$$$ is equal to product of all elements of array $$$b$$$: $$$a_1 \cdot a_2 \cdot \ldots \cdot a_n = b_1 \cdot b_2 \cdot \ldots \cdot b_k$$$;
All elements of array $$$b$$$ are integers greater than $$$1$$$ and strongly composite;
The size $$$k$$$ of array $$$b$$$ is the maximum possible.

Find the size $$$k$$$ of array $$$b$$$, or report, that there is no array $$$b$$$ satisfying the conditions.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the size of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integer $$$a_1, a_2, \dots a_n$$$ ($$$2 \le a_i \le 10^7$$$) — the array $$$a$$$ itself.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$.

Output

For each test case, print the size $$$k$$$ of array $$$b$$$, or $$$0$$$, if there is no array $$$b$$$ satisfying the conditions.

Note

In the first test case, we can get array $$$b = [18]$$$: $$$a_1 \cdot a_2 = 18 = b_1$$$; $$$18$$$ is strongly composite number.

In the second test case, we can get array $$$b = [60]$$$: $$$a_1 \cdot a_2 \cdot a_3 = 60 = b_1$$$; $$$60$$$ is strongly composite number.

In the third test case, there is no array $$$b$$$ satisfying the conditions.

In the fourth test case, we can get array $$$b = [4, 105]$$$: $$$a_1 \cdot a_2 \cdot a_3 = 420 = b_1 \cdot b_2$$$; $$$4$$$ and $$$105$$$ are strongly composite numbers.

Strongly Composite

Examples