Minimum Block Exchange Sorting

You are the famous sorting master and have been challenged by a young sorter from a neighboring land. You are given a permutation (a_1, a_2, \dots, a_n) and you are allowed to perform the following operation to sort the permutation in ascending order (i.e. to obtain (1,2,\dots,n)):

Choose indices (1 \le i \le j < k \le l \le n) and swap the two subarrays (a_{i \sim j}) and (a_{k \sim l}). After the swap, the sequence becomes: [ a_{1\sim i-1}, ; a_{k\sim l}, ; a_{j+1\sim k-1}, ; a_{i\sim j}, ; a_{l+1\sim n}. ]

It has been observed that the minimum number of operations needed to sort the permutation can be determined by the following conditions:

1. If the permutation is already sorted, the answer is (0).
2. Else if (a_1 = 1) or (a_n = n), the answer is (1).
3. Else if (a_1 = n) and (a_n = 1), the answer is (3).
4. Otherwise, the answer is (2).

Your task is to apply this strategy for each test case and output the minimum number of operations required.

inputFormat

The input begins with an integer (t) ((1 \le t \le 10^4)) on a single line, denoting the number of test cases. For each test case:

• The first line contains an integer (n) ((1 \le n \le 10^5)), the size of the permutation.
• The second line contains (n) space-separated integers (a_1, a_2, \dots, a_n), which form a permutation of ({1,2,\dots,n}).

outputFormat

For each test case, output a single integer on a new line — the minimum number of operations required to sort the permutation.

sample

1
3
1 2 3

0