BerPhone X практически готов к выпуску, на телефоне предустановлено n приложений. Категория приложения характеризует жанр или тему этого приложения (например, "игра", "бизнес" или "образование"). Категории заданы целыми числами от 1 до n включительно; i - ое приложение имеет категорию ci.
Вы можете выбрать m — количество экранов и s — размер каждого экрана. Вам необходимо разместить все n значков приложений (один значок представляет одно приложение), отвечающие следующим требованиям:
На каждом экране все значки должны принадлежать приложениям одной категории (но разные экраны могут содержать иконки приложений одной и той же категории);
Каждый экран должен быть либо полностью заполнен значками (количество значков на экране s), либо почти быть заполненным значками (количество значков равно s−1).
Ваша задача — найти минимально возможное количество экранов m.
Первая строка содержит количество тестов t (1≤t≤10000). Затем идут t тестов.
Первая строка каждого теста содержит целое число n (1≤n≤2⋅106) — количество иконок. Вторая строка содержит n целых чисел c1,c2,...,cn (1≤ci≤n), где ci — категория i-го приложения.
Гарантируется, что сумма значений n для всех тестов не превышает 2⋅106.
Выведите t целых чисел — ответы на запросы. Ответом на тест является целое число m — минимальное количество экранов, на которых могут быть размещены все n значков, удовлетворяющих заданным требованиям.