Canadian Computing Competition: 1997 Stage 2, Day 1, Problem 2

Earth is being invaded by space aliens. Earth defence forces have rallied a number of anti-spacecraft guns. However, they have a bug in their aiming hardware: initially they are aimed straight up, and this aim can only be adjusted downward.

Thousands of alien craft are streaking towards Earth as we speak -- and yes, some of them are even aimed at Canada. The Earth defence forces must now come into play. Each gun can fire as many shots as necessary, and can be re-fired as often and as quickly as necessary, but only to the same or lower setting. Thus if a spacecraft came in at height $3$ and then another at height $2$, one gun could eliminate both, but could not if they came in the other order. The Earth has only a finite number of guns and it is unknown how many alien craft are coming in. Thus they need a way to minimize the number of guns for a given set of incoming alien craft. Guess what? This is where you come in!

Input Specification

The data will consist of several sets of data. The first line will contain $T$ $(1\le T\le 5)$, the number of test cases. The first line of each set will contain one positive integer $n$ $(1\le n\le {10}^5)$, where $n$ is the number of incoming alien craft. The next $n$ lines will contain one integer number giving the heights of the incoming alien craft in order of arrival that are less than ${10}^9$ (i.e., the order the guns must eliminate them).

Output Specification

For each set, output one integer specifying the minimum number of guns required to eliminate EVERY alien craft.

Sample Input

1
10
4
2
3
4
5
3
1
4
2
5

Sample Output

4