出处：https://acs.jxnu.edu.cn/contest/24/board/challenge/B

Fun with Even Subarrays

描述：

You are given an array a">aa of n">nn elements. You can apply the following operation to it any number of times:

a">n">给你一个由n个元素组成的数组。您可以对其应用以下操作任意次数：（我觉得最重要的就是理解下面这句话：）

• Select some subarray from a">a of even size 2k">2k that begins at position l">l (1≤l≤l+2⋅k−1≤n">1≤l≤l+2?k?1≤n1≤l≤l+2?k?1≤n, k≥1">k≥1k≥1) and for each i">i between 0">0 and k−1">k?1 (inclusive), assign the value al+k+i">al+k+ial+k+i to al+i">al+ial+i.
• a">2k">l">1≤l≤l+2⋅k−1≤n">k≥1">i">0">k−1">al+k+i">al+i">在数组中从下标l开始，选择偶数大小的子数组，且对于i从1到k-1,将a(l+k+i)的值赋给a(l+i);

For example, if a=[2,1,3,4,5,3]">a=[2,1,3,4,5,3]a=[2,1,3,4,5,3], then choose l=1">l=1l=1 and k=2">k=2k=2, applying this operation the array will become a=[3,4,3,4,5,3]">a=[3,4,3,4,5,3]a=[3,4,3,4,5,3].

Find the minimum number of operations (possibly zero) needed to make all the elements of the array equal.

例如，如果a=[2,1,3,4,5,3]，则选择l=1和k=2，应用此操作，数组将成为a=[3,4,3,4,5,3]。

找到使数组的所有元素相等所需的最小操作数（可能为零）。

输入：

The input consists of multiple test cases. The first line contains a single integer t">tt (1≤t≤2⋅104">1≤t≤2?1041≤t≤2?104) — the number of test cases. Description of the test cases follows.

The first line of each test case contains an integer n">nn (1≤n≤2⋅105">1≤n≤2?1051≤n≤2?105) — the length of the array.

The second line of each test case consists of n">nn integers a1,a2,…,an">a1,a2,…,ana1,a2,…,an (1≤ai≤n">1≤ai≤n1≤ai≤n) — the elements of the array a">aa.

It is guaranteed that the sum of n">nn over all test cases does not exceed 2⋅105">2?1052?105.

输入由多个测试用例组成。第一行包含一个整数t（1≤T≤2.?104）-测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数n（1）≤N≤2.?105）-数组的长度。

每个测试用例的第二行由n个整数a1、a2、…、an（1）组成≤人工智能≤n） -数组a的元素。

保证所有测试用例中n的总和不超过2?105

输出：

Print t">tt lines, each line containing the answer to the corresponding test case — the minimum number of operations needed to make equal all the elements of the array with the given operation.

打印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

注释：

In the first test, all elements are equal, therefore no operations are needed.

In the second test, you can apply one operation with k=1">k=1k=1 and l=1">l=1l=1, set a1:=a2">a1:=a2a1:=a2, and the array becomes [1,1]">[1,1][1,1] with 1">11 operation.

In the third test, you can apply one operation with k=1">k=1k=1 and l=4">l=4l=4, set a4:=a5">a4:=a5a4:=a5, and the array becomes [4,4,4,4,4]">[4,4,4,4,4][4,4,4,4,4].

In the fourth test, you can apply one operation with k=1">k=1k=1 and l=3">l=3l=3, set a3:=a4">a3:=a4a3:=a4, and the array becomes [4,2,3,3]">[4,2,3,3][4,2,3,3], then you can apply another operation with k=2">k=2k=2 and l=1">l=1l=1, set a1:=a3">a1:=a3a1:=a3, a2:=a4">a2:=a4a2:=a4, and the array becomes [3,3,3,3]">[3,3,3,3][3,3,3,3].

In the fifth test, there is only one element, therefore no operations are needed.

注释：

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

在第二个测试中，您可以应用一个k=1和l=1的操作，设置a1:=a2，数组将通过一个操作变成[1,1]。

在第三个测试中，可以应用一个k=1和l=4的操作，设置a4:=a5，数组变成[4,4,4,4]。

在第四个测试中，您可以应用一个k=1和l=3的操作，设置a3:=a4，数组变为[4,2,3,3]，然后您可以应用另一个k=2和l=1的操作，设置a1:=a3，a2:=a4，数组变为[3,3,3,3]。

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