A. Вопреки различиям
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовём блоком массив, в котором все элементы равны длине массива. Например, $$$[3, 3, 3]$$$, $$$[1]$$$ и $$$[4, 4, 4, 4]$$$ являются блоками, в то время как $$$[1, 1, 1]$$$ и $$$[2, 3, 3]$$$ — нет.

Массив называется аккуратным, если его можно получить путём конкатенации произвольного количества блоков (возможно, нуля). Обратите внимание, что пустой массив всегда является аккуратным.

Вам дан массив $$$a$$$, состоящий из $$$n$$$ целых чисел. Найдите длину его самой длинной аккуратной подпоследовательности$$$^{\text{∗}}$$$.

$$$^{\text{∗}}$$$Последовательность $$$c$$$ является подпоследовательностью $$$a$$$, если $$$c$$$ может быть получена из $$$a$$$ удалением нескольких (возможно, ни одного или всех) элементов на произвольных позициях.

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

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

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$) — длина массива $$$a$$$.

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

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

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

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

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

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

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

В третьем наборе входных данных весь массив $$$[2,2,1,1]$$$ является аккуратным, потому что это конкатенация трёх блоков: $$$[2,2]$$$, $$$[1]$$$ и $$$[1]$$$.

В четвёртом наборе входных данных одной из самых длинных аккуратных подпоследовательностей массива $$$a$$$ является $$$[1, 3, 3, 3, 1]$$$.

В пятом наборе входных данных самой длинной аккуратной подпоследовательностью массива $$$a$$$ является пустая подпоследовательность.