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

Алиса и Боб играют в игру. Изначально есть $$$n$$$ тортов, у $$$i$$$-го из них вкусность равна $$$a_i$$$.

Алиса и Боб по очереди их едят, первой начинает Алиса:

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

Игра заканчивается, когда текущий игрок не может съесть подходящий торт. Пусть $$$x$$$ это число тортов, съеденных Алисой. Тогда Алиса хочет максимизировать $$$x$$$, в то время как Боб хочет минимизировать $$$x$$$.

Сколько тортов съест Алиса, если оба игрока будут выбирать торты оптимально?

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 5000$$$) — количество тортов.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — значения вкусностей тортов.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$5000$$$.

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

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

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

В первом наборе входных данных одна возможная последовательность ходов — следующая:

  1. Алиса съедает торт со вкусностью $$$1$$$. Остались торты со вкусностями $$$[4, 2, 3]$$$.
  2. Боб съедает торт со вкусностью $$$2$$$. Остались торты со вкусностями $$$[4, 3]$$$.
  3. Алиса съедает торт со вкусностью $$$3$$$. Остались торты со вкусностями $$$[4]$$$.
  4. Боб съедает торт со вкусностью $$$4$$$. Остались торты со вкусностями $$$[]$$$.
  5. Так как больше тортов нет, игра на этом заканчивается.

Во втором наборе входных данных одна возможная последовательность ходов — следующая:

  1. Алиса съедает торт со вкусностью $$$1$$$. Остались торты со вкусностями $$$[1, 1]$$$.
  2. Боб съедает торт со вкусностью $$$1$$$. Остались торты со вкусностями $$$[1]$$$.
  3. Так как Алиса уже съела торт со вкусностью $$$1$$$, она не может сделать ход, поэтому игра на этом заканчивается.