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

Дан массив $$$a$$$ целых чисел размера $$$n$$$. Вы можете выполнять следующую операцию неограниченное количество раз:

  • Выбрать некоторый подмассив $$$a$$$ четного размера $$$2k$$$, начинающийся в позиции $$$l$$$ ($$$1\le l \le l+2\cdot{k}-1\le n$$$, $$$k \ge 1$$$) и для каждого $$$i$$$, лежащего между $$$0$$$ и $$$k-1$$$ (включительно), присвоить значение $$$a_{l+k+i}$$$ элементу $$$a_{l+i}$$$.

Например, при $$$a = [2, 1, 3, 4, 5, 3]$$$ и выборе $$$l = 1$$$ и $$$k = 2$$$, проделывая описанную операцию, получим $$$a = [3, 4, 3, 4, 5, 3]$$$.

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

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

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

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

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

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

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

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

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

В первом наборе входных данных все элементы массива равны, следовательно, никаких операций не требуется.

Во втором наборе можно выполнить операцию с $$$k=1$$$ и $$$l=1$$$, присвоив $$$a_1 := a_2$$$, и массив станет равным $$$[1, 1]$$$ за $$$1$$$ операцию.

В третьем наборе можно выполнить операцию с $$$k=1$$$ и $$$l=4$$$, присвоив $$$a_4 := a_5$$$, и массив станет равным $$$[4, 4, 4, 4, 4]$$$.

В четвертом наборе можно выполнить операцию с $$$k=1$$$ и $$$l=3$$$, присвоив $$$a_3 := a_4$$$ и получив массив, равный $$$[4, 2, 3, 3]$$$. Затем можно выполнить операцию с $$$k=2$$$ и $$$l=1$$$, присвоив $$$a_1 := a_3$$$, $$$a_2 := a_4$$$ и получив массив, равный $$$[3, 3, 3, 3]$$$.

В пятом наборе массив состоит только из одного элемента, поэтому никаких операций не требуется.