Minimum Operations to Achieve Perfect Square Product

You are given several test cases. In each test case, you are given a positive integer n and a list of n positive integers. You can perform an operation on any integer by multiplying it by a prime number. The goal is to make the product of all the integers a perfect square.

A number is a perfect square if in its prime factorization every prime factor appears with an even exponent. In other words, if the product is written as

$$\prod_{i} p_i^{a_i},$$

then it is a perfect square if and only if \(a_i\) is even for all \(i\). Your task is to determine the minimum number of operations required to achieve this property.

Note: In one operation, you can choose any integer from the list and multiply it by any prime number. This will effectively increase the exponent of that prime factor by 1 in the overall product.

inputFormat

The input is read from standard input (stdin) and is formatted as follows:

T
n
a1 a2 ... an
... (repeated T times)

The first line of input contains a single integer T (the number of test cases). For each test case, the first line contains a positive integer n (the number of integers), followed by a line with n space-separated positive integers.

outputFormat

For each test case, output a single line containing one integer: the minimum number of operations required to make the product of all given integers a perfect square. The outputs for different test cases should be printed on separate lines.

## sample

1
3
2 2 3

1

</p>