Delete and Append Sort

Seonjong learned a new sorting algorithm in a lecture. The algorithm sorts an array by repeatedly deleting one element and inserting it again. Seonjong named the method delete and append sort.

One delete and append step has three stages.

1. Choose one element of the array.
2. Delete that element from the array.
3. Insert that element at the very end of the array.

Repeat the step until the array is sorted in ascending order. The same value can appear several times, so the array counts as sorted when no value is larger than the value right after it. For each array, find the smallest number of delete and append steps that sorts it.

The first line has the number of test cases $P$ ($1 \le P \le 100$). The $P$ data sets follow, and each data set is handled independently.

The first line of a data set has the data set number $K$ and the array length $N$ ($1 \le N \le 1000$), separated by a space.

The $N$ positive integers of the array follow on the next lines. Every line except the last one has 10 integers, and the last line has fewer than 10. Each integer is smaller than $10^9$. The same value can be given several times.

For each data set, print the data set number $K$ and the smallest number of delete and append steps on one line, separated by a space.

Take the array 1 3 2 of length 3. Delete 3 and insert it at the end, and the array becomes 1 2 3, which is sorted. Only one step was used, so the answer for this array is 1.