Bubble Divider

Time Limit: 1 Second    Memory Limit: 131072 KB

“Bubble Trouble” is the name of an old famous game which can still be played online (just Google it after the contest). Milad likes this game too much and has developed a new game “Bubble Divider” based on the old game. In each level of bubble divider there are i bubbles of size s_i which are bouncing. The player must shoot these bubbles until they disappear while trying to avoid being hit by the other bouncing bubbles. Shooting to a bubble of size s results in one of the followings:

· If s is a prime number or equals to 1, then the target bubble will disappear.

· If s is not a prime number, then the target bubble will divide into a bubbles of size b where:

s = a × b and b is the maximum possible divisor less than s.

The player must keep shooting the bubbles until all of them disappears. For example, a game level in which there is a bubble of size 9 can be cleared using 4 bullets as follows:

1. Shooting the bubble of size 9 (results in producing 3 bubbles of size 3)

2. Shooting the first bubble of size 3 (3 is prime, so the bubble will disappear).

3. Shooting the second bubble of size 3.

4. Shooting the last bubble of size 3.

Your task is to write a program to compute minimum number of bullets needed to clear a level in “Bubble Divider” game.

Input

First line of the input contains an integer N which is number of test cases. First line of each test case contains an integer b (1 <= b <= 20) denoting number of bubbles in the level. The second line of each test case contains b space separated integers denoting bubble sizes. Bubble sizes are integers between 1 and 1000.

Output

For each test case, print a line containing minimum number of bullets needed to clear the level.

Sample Input

3
1
9
2
8 9
3
6 7 8

Sample Output

4
11
11

Submit