P10488 [BAPC 2006 Qualifier] Booksort

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.

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.

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.

$1 \le T \le 3$, $1 \le n \le 15$。 Translated by ChatGPT 5