Minimum Operations to Sort Sequence

You are given a sequence of integers. In one operation you may select any contiguous subarray and reverse it. It turns out that for this problem, if the sequence is already non-decreasing (i.e. sorted in ascending order), then no operation is needed, and if it is not, one reversal operation is always sufficient to sort the sequence.

Your task is to determine the minimum number of operations required to transform the given sequence into a non-decreasing sequence. In other words, output 0 if the sequence is already sorted in non-decreasing order; otherwise, output 1.

Note: Even though reversing arbitrary segments might sometimes require more than one operation in general, it is guaranteed for the purpose of this problem that if the sequence is not already sorted, one operation is enough to sort it.

Examples:

• For the sequence [2, 4, 1, 3, 5], the output is 1.
• For the sequence [3, 1, 2, 4], the output is 1.
• For the sequence [1, 2, 3, 4, 5] or [1, 1, 1, 1], the output is 0.

You will need to process multiple test cases. See the input and output format for details.

inputFormat

The first line of the input contains an integer T (T ≥ 1) — the number of test cases. Each test case starts with an integer n — the length of the sequence, followed by a line containing n space‐separated integers.

For example:

3
5
2 4 1 3 5
4
3 1 2 4
5
1 2 3 4 5

outputFormat

For each test case, output a single integer — the minimum number of operations needed to make the sequence non-decreasing. Print each answer on a new line.

For the sample input above, the output should be:

1
1
0

## sample

3
5
2 4 1 3 5
4
3 1 2 4
5
1 2 3 4 5

1
1
0

</p>