Given a permutation of length . In one operation, you can choose at most four elements from the permutation and swap their positions arbitrarily. What is the minimum number of operations required to sort the permutation in ascending order?

A permutation of length is an array consisting of distinct integers from to in arbitrary order. For example, is a permutation, but is not a permutation ( appears twice in the array), and is also not a permutation ( but there is in the array).

输入描述:

Each test contains multiple test cases. The first line contains the number of test cases  (). The description of the test cases follows.

The first line of each test case contains an integer  (), indicating the length of the permutation.

The second line contains a permutation .

It is guaranteed that the sum of  across all test cases does not exceed .

输出描述:

For each test case, output a single integer, indicating the minimum number of operations required to sort the permutation.

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

1
1
3
2