Room Number 13

Many hotels around the world skip the number 13 and go straight to 14 when numbering rooms. This is true for other tall buildings as well. It is because of the disorder triskaidekaphobia and a general dislike of or superstition regarding the number 13.

This time our hotel "Akhalia International Hotel” numbered a room "13". This room is a special room as an infinite number of people can stay in this room. The hotel will be opened for $n$ days. Every day a people with strength $x$ will enter the room and he will start kicking out people from the room. But he is clever enough to understand that he cannot kick out a person with higher strength. So, he will not mess with them. He will eliminate others from the room. After $n$ days this room will be closed and the persons who will be present there will pay the rent to the hotel authority.

Now hotel authority appointed you to write a program to determine how many people will pay them?

Input

The first line of the input will contain the number of test cases $T$ ($0 < T \le 10$).

Each test case will start with an integer $n$ ($1 \le n \le 10^5$), the number of days.

Next line will contain n integers. Here $i$-th integer determines the strength of the person who comes on $i$-th day. All the strength will be a positive integer less than $10^9$.

Output

For each test case print a line containing the answer.

Sample

Input	Output
2 3 3 1 2 4 4 3 2 1	2 4