J. Game of Primes
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Ammar and Antwan are playing a game with two multisets $$$a$$$ and $$$b$$$, initially $$$a$$$ contains $$$n$$$ integers and $$$b$$$ is empty.

Define $$$F(x)$$$ as the greatest divisor of $$$x$$$ less than $$$x$$$, in other words, the greatest $$$y$$$ such that $$$y \lt x$$$ and $$$y$$$ divides $$$x$$$ .

The game proceeds as follows: the players take turns with Ammar starting. On each turn, a player will perform the following operation:

  • Choose an integer $$$x$$$ from multiset $$$a$$$, remove it and either add $$$F(x)$$$ or $$$\frac{x}{F(x)}$$$ to $$$b$$$.

Ammar loves primes and wants to maximize the number of primes in $$$b$$$, while Antwan hates primes and wants to minimize this number. In their universe, the number $$$1$$$ is considered a prime number.

Determine the number of primes (considering $$$1$$$ a prime ) in $$$b$$$ after the game ends if both players play optimally.

Input

The first line contains one integer $$$t \: (1 \le t \le 10^3)$$$ — the number of test cases.

The first line of each test case consists of a single integer $$$n \: (1 \le n \le 10^5)$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n \: (2 \le a_i \le 10^6)$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$.

Output

For each test case, output the number of primes (considering 1 a prime) in $$$b$$$ after the game ends if both players play optimally.

Example
Input
2
5
2 3 20 30 5
2
10 5
Output
4
2