Just Arrange the Icons#9589
BerPhone X is almost ready for release with 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 and , inclusive; the -th application has category c_i.
You can choose — the number of screens and — the size of each screen. You need to fit all 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 ) 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 .
The first line contains the number of test cases t~(1 \le t \le 10000). Then test cases follow.
The first line of each test case contains an integer n~(1 \le n \le 2 \cdot 10^6) — the number of the icons. The second line contains integers c_1, c_2, ..., c_n~(1 \le c_i \le n), where c_i is the category of the -th application.
It is guaranteed that the sum of the values of for all test cases in the input does not exceed 2 \cdot 10^6.
Print 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 — the minimum number of screens on which all icons can be placed satisfying the given requirements.
Example 1