BerPhone X практически готов к выпуску, на телефоне предустановлено приложений. Категория приложения характеризует жанр или тему этого приложения (например, "игра", "бизнес" или "образование"). Категории заданы целыми числами от до включительно; - ое приложение имеет категорию .
Вы можете выбрать — количество экранов и — размер каждого экрана. Вам необходимо разместить все значков приложений (один значок представляет одно приложение), отвечающие следующим требованиям:
На каждом экране все значки должны принадлежать приложениям одной категории (но разные экраны могут содержать иконки приложений одной и той же категории);
Каждый экран должен быть либо полностью заполнен значками (количество значков на экране ), либо почти быть заполненным значками (количество значков равно ).
Ваша задача — найти минимально возможное количество экранов .
Первая строка содержит количество тестов . Затем идут тестов.
Первая строка каждого теста содержит целое число — количество иконок. Вторая строка содержит целых чисел , где — категория -го приложения.
Гарантируется, что сумма значений для всех тестов не превышает .
Выведите целых чисел — ответы на запросы. Ответом на тест является целое число — минимальное количество экранов, на которых могут быть размещены все значков, удовлетворяющих заданным требованиям.