Problem Description

Given $n$ books numbered from $1$ to $n$.

In the initial state, the books are in an arbitrary permutation.

In each operation, you may take a consecutive segment of books and insert this segment into some other position.

The target state is to arrange the books in order from $1$ to $n$.

Find the minimum number of operations needed.

Input Format

The first line contains an integer $T$, meaning there are $T$ test cases.

Each test case contains two lines. The first line is an integer $n$, meaning the number of books.

The second line contains $n$ integers, representing an arbitrary permutation of $1 \sim n$.

Numbers on the same line are separated by spaces.

Output Format

For each test case, output the minimum number of operations.

If the minimum number of operations is greater than or equal to $5$, output 5 or more.

Each result occupies one line.

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

2
3
5 or more

Hint

$1 \le T \le 3$, $1 \le n \le 15$。

Translated by ChatGPT 5