2.2 Grocery Crates

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.

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.

Constraints

1 <= t <= 10

1 <= n <= 5000

1 <= a[i] <= 10^9

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]

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

Print the minimum possible number of visible crates

Example 1

Input:

2

3

1 2 3

4

4 2 4 3

Output:

1

2

Explanation:

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.

2

3

1 2 3

4

4 2 4 3

Output:

1

2

Explanation:

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.