В музее цифровых редкостей готовят новую витрину. У хранителя есть n экспонатов, и для каждого экспоната известен его номер типа a_i.

Нужно разложить все экспонаты в один ряд. После этого музей оценивает красоту раскладки следующим образом:

• рассматривается длина наибольшей строго возрастающей подпоследовательности в получившемся ряду;
• отдельно рассматривается длина наибольшей строго возрастающей подпоследовательности в ряду, если посмотреть на него справа налево.

Красота раскладки равна минимуму из этих двух величин.

Хранитель может переставить экспонаты в любом порядке.

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

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

В первой строке записано целое число t — количество наборов.

Далее следуют описания наборов.

Первая строка каждого набора содержит целое число n — количество экспонатов.

Вторая строка каждого набора содержит n целых чисел a_1, a_2, ..., a_n — номера типов экспонатов.

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

Для каждого набора выведите одно целое число — максимальную красоту, которую можно получить после оптимальной перестановки.

Ограничения

• 1 <= t <= 10^4
• 1 <= n <= 2 * 10^5
• 1 <= a_i <= 10^9
• сумма всех n по всем наборам не превосходит 2 * 10^5

Пример

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

3
4
1 1 2 3
4
1 1 1 1
3
1 2 3

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

2
1
2

Пояснение

В первом наборе два экспоната типа 1 позволяют поддержать рост и слева направо, и справа налево, а типы 2 и 3, встречающиеся по одному разу, можно распределить между двумя сторонами.

Во втором наборе все экспонаты одного типа, поэтому длина любой строго возрастающей подпоследовательности не может быть больше 1.

В третьем наборе все типы различны, и оптимально распределить их так, чтобы минимум из двух рассматриваемых величин был равен 2.