Minimum Operations to Sort Books

In this problem, you are given (T) test cases. For each test case, you are provided with an integer (n) representing the number of books, and a list of (n) integers representing the thickness of the books. The books should be arranged in non-decreasing order (i.e. sorted in increasing order).

You are allowed to perform at most one reversal operation on a contiguous subsegment of the books to try to achieve the sorted order. If reversing a specific segment yields a sorted list, the answer is 1. If the books are already sorted, the answer is 0, otherwise the answer is 2 (indicating that one reversal operation is not sufficient to sort the list completely after adjusting the misplaced portion).

Formally, let the original list be (A = [a_1, a_2, \dots, a_n]) and the sorted list be (B). Define (i) as the smallest index such that (a_i \neq b_i) and (j) as the largest index such that (a_j \neq b_j). If reversing the subarray (A[i\dots j]) results in (B), then the minimum number of operations required is 1, otherwise it is 2 (if the list is not already sorted).

inputFormat

The input is read from standard input (stdin).

The first line contains an integer (T) indicating the number of test cases. For each test case, the input is structured as follows:
- The first line of each test case contains an integer (n): the number of books.
- The second line contains (n) space-separated integers representing the thicknesses of the books.

outputFormat

For each test case, output a single integer on a new line representing the minimum number of operations required to sort the list of books. The output is written to standard output (stdout).## sample

1
4
1 2 3 4

0