Towers

You are given ‘N’ cubes in an array ‘ARR’ in a certain order, and your task is to build towers using them. Whenever two cubes are on top of the other, the upper cube must be smaller than the lower cube.

You must process the cubes in the given order. You can always either place the cube on top of an existing tower or begin a new tower. What is the minimum possible number of towers?

For example:

Given ‘N’ = 3, ‘ARR’[] = 3, 2, 1.
The answer will be one because you can stack one over two over 3. Therefore only these can be inserted in the same tower.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains a single integer ‘N’, where ‘N’ is the number of elements of the array.

The second line of each test case contains ‘N’ space-separated integers, denoting the array elements.

Output format:

For each test case, print a single line containing a single integer denoting the minimum possible number of towers.

The output of each test case will be printed in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 2000
1 <= ARR[ i ] <= 2000

Where ‘T’ is the total number of test cases, and 'N’ is the length of the array, and ‘ARR[ i ]’ is the array element at index ‘i’.

Time limit: 1 second.