Lucifer is as bored as G-One after the defeat of Raone. he has no computer game to play. He Like g-One started reading books and Unlike G-One he bought a big book shelf and lots of books. He labelled all books with serial numbers. (All books have different serial numbers).

He invites his friends and small kids to home and allows them to read books. But the problem is everyone replaces the books anywhere on the shelf.

At the end of the day Lucifer has to sort all the books in increasing order of serial number on the shelf from left to right. The problem is he knows just one way of sorting called LUCIFER SORT.

He can pick a book from anywhere on the shelf but can replace it only in the center of the remaining books.

For example of the books are in order: 2 1 3 4 5 6

The steps of sorting are

• 1 3 4 2 5 6  -  Pick 2 and place between between 4 and 5 in (1 3 4 5 6)
• 1 4 2 3 5 6  -  Pick 3 and place between between 2 and 5 in (1 4 2 5 6)
• 1 2 3 4 5 6  -  Pick 4 and place between between 3 and 5 in (1 2 3 5 6)

Assuming positions are numbered from 1 to N.

While replacingm, if number of books left is even then it is put back between n/2 and n/2+1 position. If the number of books left is odd, it is put back between (n+1)/2 and (n+1)/2+1 position.

Since the number of books are large, he needs your help to tell me number of steps he needs to sort the shelf.

Input

First line contains number of shelves.

For each shelf there are 2 lines:

First line will have number of books.

Second line will have the serial number of the books at the end of the day.

Output

Single line telling how many books he needs to remove and replace.

If there is no way he can sort the books by this process Print "YOU ARE DOOMED" without the quotes.

Example

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

Output:
0
3
6

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