Chắc hẳn bạn nào học tin cũng biết đến thuật toán sàng số nguyên tố sau đây khi được học đến phần số học. Dưới đây là mã giả của thuật toán sàng:

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])

Bí quyết để ghi nhớ thuật toán này, cũng như để chứng minh được tính đúng đắn, là khi duyệt đến một giá trị ~v~ bất kỳ, ta đánh dấu tất cả các bội của ~v~ là hợp số.

Sau khi giảng cho bạn thuật toán này, thầy giáo đã rất kinh ngạc khi thấy bạn đã hiểu và có khả năng áp dụng nó rất nhanh. Thầy giáo đành phải ra thêm bài tập bổ sung xoay quanh thuật toán này. Mỗi bài tập của thầy giáo gồm số nguyên ~n~ và mảng số nguyên ~a~ là hoán vị~^*~ của ~n - 1~ số nguyên ~[2, 3, \ldots, n]~. Thầy giáo muốn bạn thay đổi mảng ~a~, sao cho khi thực hiện thuật toán ~\mathtt{sieve}(n, a)~, kết quả thu được là một danh sách chỉ bao gồm số nguyên tố.

Để làm điều này, thầy giáo cho phép bạn thực hiện thao tác sau (không hoặc nhiều lần):

• Chọn hai phần tử kề nhau trong ~a~ sao cho có chính xác một phần tử được chọn là số nguyên tố và phần tử còn lại là hợp số, rồi hoán đổi vị trí của hai phần tử này.

Ví dụ, với ~a = [\underline{2}, 4, \underline{5}, \underline{3}, 8, 6, \underline{7}]~, được phép đổi chỗ cặp phần tử ~(2, 4)~, ~(4, 5)~, ~(3, 8)~ hoặc ~(6, 7)~. Các cặp phần tử sau không được phép đổi chỗ:

• ~(4, 3)~, do chúng không kề nhau,

• ~(5, 3)~, do chúng cùng là số nguyên tố,

• ~(8, 6)~, do chúng cùng là hợp số.

Thầy giáo muốn bạn giải đáp bài tập càng nhanh càng tốt. Do đó với mỗi câu đố, bạn muốn tìm xem cần thực hiện ít nhất bao nhiêu thao tác để giải đáp bài tập đó. Có thể chứng minh được rằng với mọi mảng ~a~ hợp lệ, tồn tại mỗi dãy các thao tác đổi chỗ sao cho ~\mathtt{sieve}(n, a)~ là một danh sách chỉ bao gồm số nguyên tố.

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

~^*~ Một hoán vị của một dãy là một dãy khác có cùng tập hợp các phần tử (bao gồm cả các phần tử trùng lặp, nếu có), nhưng có thể được sắp xếp theo bất kỳ thứ tự nào. Ví dụ, ~[1, 2, 2, 3]~, ~[2, 3, 1, 2]~, và ~[2, 2, 1, 3]~ là một số hoán vị của ~[3, 2, 1, 2]~, nhưng ~[2, 4, 3, 1]~, ~[2, 1, 2]~, và ~[1, 1, 2, 3]~ thì không.

Input

Dòng đầu tiên gồm số nguyên ~t~ (~1 \le t \le 10\,000~) – số lượng bài tập thầy giáo ra cho bạn. Mô tả của mỗi bài tập như sau.

Dòng đầu tiên gồm số nguyên ~n~ (~2 \le n \le 10^6~).

Dòng thứ hai gồm ~n - 1~ số nguyên ~a_1, a_2, \ldots, a_{n - 1}~ (~2 \le a_i \le n~, ~a_i \ne a_j~ với mọi ~i \ne j~).

Đảm bảo rằng tổng ~n~ qua tất cả các bài tập không quá ~10^6~.

Output

Với mỗi bài tập, in ra số thao tác hoán đổi phần tử mảng ~a~ ít nhất, sao cho ~\mathtt{sieve}(n, a)~ là một danh sách chỉ bao gồm số nguyên tố.

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

Trong bài tập đầu tiên, ta có ~a = [3, 2]~. Ta không cần sử dụng thêm thao tác gì vì khi đó kết quả khi thực hiện ~\mathtt{sieve}(3, [3, 2])~ là ~[3, 2]~.

Trong bài tập thứ hai, ta có ~a = [4, 3, 2]~. Ta có thể sử dụng 2 thao tác để biến đổi ~a~ thành ~[3, 2, 4]~. Khi đó ~\mathtt{sieve}(3, [3, 2, 4]) = [3, 2]~.

Trong bài tập thứ ba, ta có thể đảo chỗ vị trí của phần tử ~6~ và ~2~.