# 2019 ACM NEERC, Semifinal

# Just Arrange the Icons

BerPhone X is almost ready for release with n applications being preinstalled on the phone. A category of an application characterizes a genre or a theme of this application (like “game”, “business”, or “education”). The categories are given as integers between **1** and **n**, inclusive; the **i**-th application has category `c`

._{i}

You can choose **m** - the number of screens and **s** - the size of each screen. You need to fit all **n** icons of the applications (one icon representing one application) meeting the following requirements:

On each screen, all the icons must belong to applications of the same category (but different screens can contain icons of applications of the same category);

Each screen must be either completely filled with icons (the number of icons on the screen is equal to

**s**) or almost filled with icons (the number of icons is equal to**s**-**1**).

Your task is to find the minimal possible number of screens **m**.

#### Input

The first line contains an integer **t** (**1** ≤ **t** ≤ **10000**) - the number of test cases in the input. Then **t** test cases follow.

The first line of each test case contains an integer **n** (**1** ≤ **n** ≤ **2** * `10`

) - the number of the icons. The second line contains ^{6}**n** integers `c`

, _{1}`c`

, ..., _{2}`c`

(_{n}**1** ≤ `c`

≤ _{i}**n**), where `c`

is the category of the _{i}**i**-th application.

It is guaranteed that the sum of the values of **n** for all test cases in the input does not exceed **2** * `10`

.^{6}

#### Output

Print **t** integers - the answers to the given test cases in the order they follow in the input. The answer to a test case is an integer **m** — the minimum number of screens on which all **n** icons can be placed satisfying the given requirements.

3 11 1 5 1 5 1 5 1 1 1 1 5 6 1 2 2 2 2 1 5 4 3 3 1 2

3 3 4