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$ значков, удовлетворяющих заданным требованиям.