In response to the recent terrorist attack in Pulwama district, Indian Army has decided to launch another surgical strike at a key terrorist launch pad. This launch pad is heavily guarded by tanks, thus an airstrike is necessary before the attack. Captain Shalaka is given this responsibility.
There are N tanks present at the war site. Each tank ‘i’ has a specific strength ‘Si’. You are in a fighter plane. The plane has ability to drop special type of a missile. You can drop missile on a tank which we will call as main target. Each missile when dropped on a tank, destroys that tank and ejects another missile horizontally either left or right and destroys all the tanks in its way that have strength less than or equal to that of the main target.
Your task is to determine the minimum no. of missiles that are required to destroy all the enemy tanks.
Constraints:
1<=T<=10
2<=N<=105
1<=Si<=109 for each valid i
Si != Sj for each i != j
The sum of N over all test cases does not exceed 5.105
Input:
First line of the input contains number of test cases T. The description of T test cases follows.
First line of each test case contains a single integer N.
The second line of each test case contains N space separated integers S1,S2,…….SN.
Output:
For each test case, output a single line containing a single integer denoting minimum number of missiles required.
Shalaka will drop one missile on 3rd canon which will eventually lead to destruction of 1st and 2nd canon and 2nd missile on 4th canon.