Minimum Moves to Sort Books

In this problem, you are given several test cases. In each test case, there is a collection of books identified by their string names. Your task is to determine the minimum number of moves required to arrange the books in alphabetical order. A move consists of relocating one book to its correct position.

The key observation is that if you can find the longest non-decreasing sequence (i.e. the longest increasing subsequence, or $LIS$) in the current order, then the minimum number of moves required equals the total number of books minus the length of this sequence. In mathematical terms, if there are $n$ books and the length of the longest increasing subsequence is $L$, then the answer is given by

inputFormat

Input is read from standard input (stdin). The first line contains an integer $T$, the number of test cases. Each test case begins with an integer $n$, the number of books, followed by a single line containing $n$ space-separated strings representing the identifiers of the books.

outputFormat

For each test case, output the minimum number of moves required to sort the books in alphabetical order. Each result should be printed on a new line to standard output (stdout).## sample

1
4
eat sleep code repeat

2