Booksort

The Leiden University Library holds millions of books. A student who wants to borrow a book usually submits an online loan form. If the book is available, he picks it up at the loan counter the next day. That is the modern way of borrowing books at this library.

One department of the library, full of bookcases, still works the old way. Students walk around there, pick out the books they like, register them, and take them home for at most three weeks.

Quite often a student takes a book from a shelf, looks at it more closely, decides not to read it, and puts it back. Not every student is careful with that last step. Every book has a unique identification code and the books in a bookcase are sorted by that code, but some students put a book they rejected back in the wrong place. They do find the right shelf. They just do not put the book at the right position on it.

Other students look up the unique identification code in an online catalogue and use it to find the books they want to borrow. For them it matters that the books really are sorted by code. It matters to the librarian too, because sorted shelves make it much easier to see whether a book is missing without having been borrowed, that is, stolen.

So every week the librarian walks through the department and sorts the books on every shelf. Sorting one shelf is doable, but it is still quite some work. He compared several algorithms and settled on sorting by transpositions, which is the easiest one for him. As long as the books are not sorted he repeats these steps:

1. take out a block of books (a number of books standing next to each other),
2. shift another block of books, from the left or the right of the resulting hole, into this hole,
3. put back the first block of books into the hole left open by the second block.

One such sequence of steps is called a transposition.

The picture below shows the steps of the algorithm. X is the first block of books and Y is the second block.

The librarian wants to keep his work down, so for every shelf he wants the smallest number of transpositions that sorts the books. In particular he wants to know whether at most 4 transpositions are enough. Can you tell him?

The first line of the input contains a single number: the number of test cases. Each test case has the following format:

• One line with one integer $n$ with $1 \le n \le 15$: the number of books on a certain shelf.
• One line with the $n$ integers $1, 2, \ldots, n$ in some order, separated by single spaces: the unique identification codes of the $n$ books in their current order on the shelf.

For every test case, print a single line containing:

• the minimal number of transpositions $T$ that sorts the books by increasing identification code, if $T \le 4$;
• the message 5 or more, if at least 5 transpositions are needed.