C. Пинки Пай поедает пирожные
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Пинки Пай купила пакет пирожных с разными начинками! Но оказалось, что не все пирожные различаются начинкой между собой, то есть в пакете есть какие-то пирожные с одинаковой начинкой.

Пинки Пай ест пирожные по одному подряд. Она любит веселиться, поэтому решила не просто поедать пирожные, а стараться не есть пирожные с одной начинкой слишком часто. Для этого она хочет, чтобы минимальное расстояние между съеденными пирожными с одинаковой начинкой было как можно больше. При этом расстоянием между двумя пирожными Пинки Пай решила назвать количество съеденных пирожных между ними.

Пинки Пай может поедать пирожные в любом порядке. Ей не терпится скорее съесть все пирожные, поэтому она просит вас помочь посчитать наибольшее минимальное расстояние между съеденными пирожными с одинаковой начинкой среди всех возможных порядков поедания!

Пинки Пай собирается покупать еще пакеты с пирожными, поэтому просит вас решить задачу для нескольких пакетов!

Входные данные

Первая строка содержит одно целое число $$$T$$$ ($$$1 \le T \le 100$$$) — количество пакетов, для которых нужно решить задачу.

Первая строка описания пакета содержит одно целое число $$$n$$$ ($$$2 \le n \le 10^5$$$) — количество пирожных в нем. Вторая строка описания пакета содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — информация о начинках пирожных: одинаковые начинки обозначены одинаковым числом, разные начинки — разным. Гарантируется, что в каждом пакете есть как минимум два пирожных с одинаковой начинкой.

Гарантируется, что сумма значений $$$n$$$ по всем пакетам не превосходит $$$10^5$$$.

Выходные данные

Для каждого пакета в отдельной выведите одно целое число — наибольшее минимальное расстояние между съеденными пирожными с одинаковой начинкой среди всех возможных порядков поедания пирожных из этого пакета.

Пример
Входные данные
4
7
1 7 1 6 4 4 6
8
1 1 4 6 4 6 4 7
3
3 3 3
6
2 5 2 3 1 4
Выходные данные
3
2
0
4
Примечание

Для первого пакета Пинки Пай может есть пирожные в следующем порядке (по начинкам): $$$1$$$, $$$6$$$, $$$4$$$, $$$7$$$, $$$1$$$, $$$6$$$, $$$4$$$ (таким образом, минимальное расстояние будет равно $$$3$$$).

Для второго пакета Пинки Пай может есть пирожные в следующем порядке (по начинкам): $$$1$$$, $$$4$$$, $$$6$$$, $$$7$$$, $$$4$$$, $$$1$$$, $$$6$$$, $$$4$$$ (таким образом, минимальное расстояние будет равно $$$2$$$).