Просто розташуйте значки

BerPhone X майже готовий до випуску, і на ньому вже встановлено $n$ застосунків. Кожен застосунок має свою категорію, яка визначає його жанр або тему (наприклад, "гра", "бізнес" або "освіта"). Категорії представлені цілими числами від $1$ до $n$ включно; $i$-й застосунок належить до категорії $c_i$.

Вам потрібно вибрати $m$ — кількість екранів, і $s$ — розмір кожного екрану. Завдання полягає в тому, щоб розмістити всі $n$ значків застосунків (кожен значок представляє один застосунок) відповідно до наступних умов:

• На кожному екрані всі значки повинні належати до однієї категорії (різні екрани можуть містити значки застосунків однієї і тієї ж категорії);

• Кожен екран повинен бути або повністю заповнений значками (кількість значків на екрані дорівнює $s$), або майже заповнений (кількість значків дорівнює $s-1$).

Ваше завдання — визначити мінімально можливу кількість екранів $m$.

Вхідні дані

Перша стрічка містить кількість тестів $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$.

Вихідні дані

Виведіть $t$ цілих чисел — відповіді на запити. Відповіддю на кожен тест є ціле число $m$ — мінімальна кількість екранів, на яких можуть бути розміщені всі $n$ значків, що задовольняють заданим умовам.

Приклади