Array Operation

Problem Description

You are given an array $a$ of $n$ elements. You may perform the following operation any number of times:

From an even-sized subarray of size $2k$ starting at position $l$ ($1 \le l \le l + 2 \cdot k - 1 \le n$, $k \ge 1$), for each $i$ from $0$ to $k-1$ inclusive, assign the value $a_{l+k+i}$ to $a_{l+i}$.

For example, if $a = [2, 1, 3, 4, 5, 3]$ and you choose $l = 1$ and $k = 2$, then after applying this operation the array becomes $a = [3, 4, 3, 4, 5, 3]$.

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

Input Format

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \le t \le 2 \times 10^4$), the number of test cases.

Each test case consists of $(n + 1)$ integers:

The first integer $n$ ($1 \le n \le 2 \times 10^5$) is the length of the array.

The following $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) are the elements of the array.

Output Format

Output $t$ lines, each containing one integer: the minimum number of operations required to make all elements equal using the given operation.

Sample Input

5
3 1 1 1
2 2 1
5 4 4 4 2 4
4 4 2 1 3
1 1

Sample Output

0
1
1
2
0

Constraints

The sum of $n$ over all test cases does not exceed $200000$.

Hint

In the first test, all elements are already equal, so no operation is needed.

In the second test, you can apply one operation with $k = 1, l = 1$, setting $a_1 \leftarrow a_2$, turning the array into $[1, 1]$ in $1$ operation.

In the third test, you can apply one operation with $k = 1, l = 4$, setting $a_4 \leftarrow a_5$, turning the array into $[4, 4, 4, 4, 4]$.

In the fourth test, you can apply one operation with $k = 1, l = 3$, setting $a_3 \leftarrow a_4$, turning the array into $[4, 2, 3, 3]$; then you can apply another operation with $k = 2, l = 1$, setting $a_1 \leftarrow a_3, a_2 \leftarrow a_4$, turning the array into $[3, 3, 3, 3]$.

In the fifth test, there is only one element, so no operation is needed.