Surely anyone studying computer science is familiar with the following Sieve of Eratosthenes algorithm when learning about number theory. Below is the pseudocode for the sieve algorithm:

function sieve(n, values):
    primes := []
    is_prime := array[2..n], initialized to true
    for v in values do:
        if not is_prime[v] then:
            continue
        end if
        append v to primes

        for i := 2 to ⌊n / v⌋ do:
            is_prime[i * v] := false
        end for
    end for
    return primes
end function

// ...
primes = sieve(n, [2, 3, ..., n])

The key to remembering this algorithm, as well as to proving its correctness, is that when iterating over any value ~v~, we mark all multiples of ~v~ as composite.

After teaching you this algorithm, the teacher was very astonished to see that you understood it and could apply it very quickly. The teacher had to assign additional exercises related to this algorithm. Each exercise consists of an integer ~n~ and an array of integers ~a~ which is a permutation~^*~ of ~n - 1~ integers ~[2, 3, \ldots, n]~. The teacher wants you to modify the array ~a~ so that when performing the algorithm ~\mathtt{sieve}(n, a)~, the result obtained is a list that only includes prime integers.

To do this, the teacher allows you to perform the following operation (zero or more times):

• Choose two adjacent elements in ~a~ such that exactly one of the chosen elements is a prime number and the other is a composite number, and then swap the positions of these two elements.

For example, with ~a = [\underline{2}, 4, \underline{5}, \underline{3}, 8, 6, \underline{7}]~, you are allowed to swap the pairs ~(2, 4)~, ~(4, 5)~, ~(3, 8)~, or ~(6, 7)~. The following pairs of elements are not allowed to be swapped:

• ~(4, 3)~, because they are not adjacent,

• ~(5, 3)~, because they are both prime numbers,

• ~(8, 6)~, because they are both composite numbers.

The teacher wants you to solve the exercise as quickly as possible. Therefore, for each puzzle, you want to find out the minimum number of operations needed to solve that exercise. It can be proven that under any possible array ~a~, there exists some sequence of swaps such that ~\mathtt{sieve}(n, a)~ is a list that only includes prime numbers.

————————————————–

~^*~ A permutation of a sequence is another sequence that has the same set of elements (including duplicate elements, if any), but can be arranged in any order. For example, ~[1, 2, 2, 3]~, ~[2, 3, 1, 2]~, and ~[2, 2, 1, 3]~ are some permutations of ~[3, 2, 1, 2]~, but ~[2, 4, 3, 1]~, ~[2, 1, 2]~, and ~[1, 1, 2, 3]~ are not.

Input

The first line contains an integer ~t~ (~1 \le t \le 10\,000~) – the number of exercises the teacher assigned to you. The description of each exercise is as follows.

The first line contains an integer ~n~ (~2 \le n \le 10^6~).

The second line contains ~n - 1~ integers ~a_1, a_2, \ldots, a_{n - 1}~ (~2 \le a_i \le n~, ~a_i \ne a_j~ for all ~i \ne j~).

It is guaranteed that the sum of ~n~ across all exercises does not exceed ~10^6~.

Output

For each exercise, print the minimum number of swap operations needed on the array ~a~ so that ~\mathtt{sieve}(n, a)~ is a list that only includes prime numbers.

Scoring

Sample Input 1

4
3
3 2
4
4 3 2
8
7 6 2 3 4 5 8
9
4 6 9 2 8 5 7 3

Sample Output 1

0
2
1
9

Notes

In the first exercise, we have ~a = [3, 2]~. We do not need to perform any additional operations because the result of executing ~\mathtt{sieve}(3, [3, 2])~ is ~[3, 2]~.

In the second exercise, we have ~a = [4, 3, 2]~. We can use 2 operations to transform ~a~ into ~[3, 2, 4]~. Then, ~\mathtt{sieve}(3, [3, 2, 4]) = [3, 2]~.

In the third exercise, we can swap the positions of the elements ~6~ and ~2~.