After Killing RaOne G-One had nothing to do. HE started reading books and became a avid book reader.

To avoid purchasing books and he started working in a library.

Every evening he had to arrange the books in the shelf in increasing order of their serial number.

Every book in a the library is is numbered .

..

G-One found a ingenious way of arranging the books.  \He can remove any book from the shelf and put it either at the beginning or at the end of the shelf..

For example if the books are arranged in the order below

2 3 1 7 4 5 6

he can make it sorted by removing '1' and placing it at the beginning and then removing '7' and placing it in the end.

Since the book shelf can be very big and can have large number of books He needs your help to tell him the minimum remove and place operations he needs to do.

Can you help him ?

Input

1st line of the input contains number 't' denoting the number of shelves in the library. 2*t lines follow this

1st line of each test case will have single number 'b' - denoting number of books on the shelf.

2nd line wil contain b numbers. each bi denoting the serial number of the book.

Output

For each test case ouput single number 'res' - denoting the minimum remove and place operations needed to arrange the shelf.

Example

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

NOTE - All the values will be in the range [0, 10^7], number of test cases <=100.