A. Nezzar и разноцветные шары
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Nezzar есть $$$n$$$ шаров, пронумерованных числами $$$1, 2, \ldots, n$$$. На них написаны числа $$$a_1, a_2, \ldots, a_n$$$, соответственно. Числа на этих шарах образуют неубывающую последовательность, то есть $$$a_i \leq a_{i+1}$$$ для всех $$$1 \leq i < n$$$.

Nezzar хочет покрасить эти шары в минимальное количество цветов так, чтобы следующее условие было выполнено.

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

Обратите внимание, что последовательность длины не больше $$$1$$$ считается строго возрастающей последовательностью.

Помогите Nezzar определить минимальное количество цветов.

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

В первой строке находится единственное целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных.

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

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

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

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

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

Будем каждому цвету сопоставлять свое число. Тогда:

В первом наборе входных данных одна из оптимальных раскрасок это $$$[1,2,3,3,2,1]$$$.

Во втором наборе входных данных одна из оптимальных раскрасок это $$$[1,2,1,2,1]$$$.