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

У Юсефа есть массив $$$a$$$ размером $$$n$$$. Он хочет разделить массив на один или несколько смежных отрезков так, чтобы каждый элемент $$$a_i$$$ принадлежал ровно одному отрезку.

Разделение называется классным, если для каждого отрезка $$$b_j$$$ все элементы в $$$b_j$$$ также присутствуют в $$$b_{j + 1}$$$ (если он существует). То есть каждый элемент в отрезке должен также присутствовать и в следующем отрезке.

Например, если $$$a = [1, 2, 2, 3, 1, 5]$$$, классное разделение, которое может сделать Юсеф, это $$$b_1 = [1, 2]$$$, $$$b_2 = [2, 3, 1, 5]$$$. Это классное разделение, потому что каждый элемент в $$$b_1$$$ (то есть $$$1$$$ и $$$2$$$) также присутствует в $$$b_2$$$. В отличие от этого, $$$b_1 = [1, 2, 2]$$$, $$$b_2 = [3, 1, 5]$$$ не является классным разделением, так как $$$2$$$ присутствует в $$$b_1$$$, но не в $$$b_2$$$.

Обратите внимание, что после разделения массива вы не изменяете порядок отрезков. Также обратите внимание, что если элемент появляется несколько раз в каком-либо отрезке $$$b_j$$$, он должен появляться хотя бы один раз в $$$b_{j + 1}$$$.

Ваша задача — помочь Юсефу, найдя максимальное количество отрезков, которые образуют классное разделение.

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

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

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

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

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

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

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

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

Первый пример разобран в условии. Мы можем разделить его на $$$b_1 = [1, 2]$$$, $$$b_2 = [2, 3, 1, 5]$$$. Можно показать, что нет другого разделения с большим количеством отрезков.

Во втором примере мы можем разделить массив на $$$b_1 = [1, 2]$$$, $$$b_2 = [1, 3, 2]$$$, $$$b_3 = [1, 3, 2]$$$. Максимальное количество отрезков равно $$$3$$$.

В третьем примере единственное разделение, которое мы можем сделать, это $$$b_1 = [5, 4, 3, 2, 1]$$$. Любое другое разделение не будет удовлетворять условию. Поэтому ответ равен $$$1$$$.