数组操作

题目描述

给你一个有 $n$ 个元素的数组 $a$ 。你可以对它进行如下操作，次数不限。

从一个偶数大小为 $2k$ 的数组中选择一些从位置 $l$ 开始的子数组($1 \leq l \leq l+2⋅k−1 \leq n$ , $k \geq 1$) ，对于 $0$ 到 $k-1$（包括）之间的每一个 $i$ ，将值 $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 \times 10^4)$表示测试用例的数量。

每个测试用例的包含 $(n+1)$ 个整数：

第一个整数 $n (1 \leq n \leq 2 \times 10^5)$ 表示数组的长度。

此后 $n$ 个整数 $a_1,a_2,...,a_n(1 \leq a_i \leq n)$ 表示数组的元素。

输出格式

输出 $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

数据范围

保证所有测试用例的 $n$ 之和不超过 $200000$。

提示

在第一个测试中，所有元素都是相等的，因此不需要任何操作。

在第二个测试中，你可以应用一个操作，$k=1，l=1$，设置 $a_1\leftarrow a_2$ ，通过 $1$ 个操作，数组变成 $[1,1]$。

在第三个测试中，你可以应用一个操作，$k=1，l=4$，设置 $a_4\leftarrow a_5$ ，然后数组变成 $[4,4,4,4,4]$。

在第四个测试中，你可以应用一个操作，$k=1，l=3$，设置 $a_3\leftarrow a_4$ ，数组变成 $[4,2,3,3]$，然后你可以应用另一个操作，$k=2，l=1$，设置 $a_1\leftarrow a_3, a_2\leftarrow a_4，$ 数组变成 $[3,3,3,3]$。

在第五次测试中，只有一个元素，因此不需要任何操作。