Traffic jam

All submissions for this problem are available.

Little Johnny has a selection of boxes. Each box has a number on its side. The boxes are placed in a sequence, and Johnny wants to sort them (in ascending order). He has a device to manipulate the boxes, which performs the following operation. Johnny can select a subset of boxes, and the machine will lift the selected subset, shift the selected subset to the right (keeping the order in the subset), shift the not-selected subset to the left, filling up empty spaces (keeping the order in the subset), then finally move the raised boxes to be in one level again.

For example: if Johnny has the sequence: 1,2,3,4,5,6, and selects the subset in bold: 1,2,3,4,5,6, then the result is: 1,2,5,3,4,6.

Help Johnny to write a program that will calculate the minimal number of moves required to sort the given sequence of boxes in ascending order of numbers.

Input

First, 1≤t≤10, the number of test cases. Then, t testcases follow. Each starts with 1≤n≤10⁵, the number of boxes. Then, n integer values describing the sizes of boxes in the sequence.

Output

For each testcase, in a separate line, print the answer to that testcase.

Example

Input:
1
6 1 3 5 2 4 6
Output:
2

---

Date:	2010-02-05
Time limit:	1s-5s
Source limit:	50000B
Languages:	All except: TCL PERL6