2.2 Grocery Crates
(RankList for this Question)
Score: 20pts
Time Limit: 5.00 sec
A local grocery store has ordered n cubical crates from a high-quality manufacturer. Now these crates need to be placed in a storeroom such that they occupy a minimum amount of space so that there is more space for other items in the near future.

The owner Shyam is going to arrange them but there are some conditions.

If crate A is to be placed in crate B then,

1. The size of crate A should be smaller than the size of crate B.
2. Crate A should not be inside any other crate.
3. Crate B should not contain any other crate.

A crate is called visible if it is not inserted in any other crate. Help Shyam to find the minimum possible visible crates.

1 <= t <= 10
1 <= n <= 5000
1 <= a[i] <= 10^9

Input Format
The first lines contain the number of test cases t

For each test case then -
The first line would contain the number of crates n
The second line contains n integers, which are the sizes of each crate a[i]

Output Format
For each test case -
Print the minimum possible number of visible crates

Example 1
1 2 3
4 2 4 3


In the first test case it is possible to put crate 1 into crate 2, and 2 into 3.
In the second test case Shyam can put crate 2 into crate 3, and crate 4 into crate 1.

Log In to solve the Question