Məsələlər
Просто расположите значки
Просто расположите значки
BerPhone X практически готов к выпуску, на телефоне предустановлено $n$ приложений. Категория приложения характеризует жанр или тему этого приложения (например, "игра", "бизнес" или "образование"). Категории заданы целыми числами от $1$ до $n$ включительно; $i$ - ое приложение имеет категорию $c_i$.
Вы можете выбрать $m$ --- количество экранов и $s$ --- размер каждого экрана. Вам необходимо разместить все $n$ значков приложений (один значок представляет одно приложение), отвечающие следующим требованиям:
\begin{itemize}
\item На каждом экране все значки должны принадлежать приложениям одной категории (но разные экраны могут содержать иконки приложений одной и той же категории);
\item Каждый экран должен быть либо полностью заполнен значками (количество значков на экране $s$), либо почти быть заполненным значками (количество значков равно $s - 1$).
\end{itemize}
Ваша задача --- найти минимально возможное количество экранов $m$.
\InputFile
Первая строка содержит количество тестов $t~(1 \le t \le 10000)$. Затем идут $t$ тестов.
Первая строка каждого теста содержит целое число $n~(1 \le n \le 2 \cdot 10^6)$ --- количество иконок. Вторая строка содержит $n$ целых чисел $c_1, c_2, ..., c_n~(1 \le c_i \le n)$, где $c_i$ --- категория $i$-го приложения.
Гарантируется, что сумма значений $n$ для всех тестов не превышает $2 \cdot 10^6$.
\OutputFile
Выведите $t$ целых чисел --- ответы на запросы. Ответом на тест является целое число $m$ --- минимальное количество экранов, на которых могут быть размещены все $n$ значков, удовлетворяющих заданным требованиям.
Giriş verilənləri #1
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
Çıxış verilənləri #1
3 3 4