$\textit$ {Life is change, change is stability.}

Chef calls a sequence of integers $A_{1}, A_{2}, \ldots, A_{N}$ stable if all the elements in the sequence are equal.

Chef gives you $a sequence A_{1}, A_{2}, \ldots, A_{N}.$ You may perform the following operations on the sequence any number of times (possibly 0):
1. Select any prefix $A[1 \ldots k]$ such that $max(A[1 \ldots k]) = A[k]$ and set A[i] :$= A[k] \forall i \in$ [1,k-1]. For example, if the sequence $A = [\textcolor{blue}{3,1,4},5,9]$ , then choosing k = 3 yields the sequence $[\textcolor{blue}{4,4,4},5,9]$ .

1. Select any segment $A[L \ldots R]$ and shift the segment cyclically to the left keeping other elements unchanged. For example, if the sequence $A = [3, \textcolor{blue}{4,1,5} ,9]$ , then choosing L = 2 and R = 4 yields the sequence $[3, \textcolor{blue}{1,5,4} ,9]$.

Chef is asking you to find the minimum number of operations required to make the sequence stable.

It is guaranteed that you can always make the sequence stable using such operations.

------ Input Format ------

• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains a single integer N.
• The second line of each test case contains $N space-separated integers A_{1}, A_{2}, \ldots, A_{N}$.

------ Output Format ------

For each test case, print the minimum number of operations required to make the sequence stable.

------ Constraints ------

$1 ≤ T ≤ 10^{3}$
$1 ≤ N ≤ 100$
$1 ≤ A_{i} ≤ 100$ for each valid $i$

----- Sample Input 1 ------
2
3
1 1 1
2
69 96
----- Sample Output 1 ------
0
1
----- explanation 1 ------
Test Case $1$: The sequence is already stable, so we require $0$ operations.

Test Case $2$: We can apply operation $1$ on the prefix $A[1 \dots 2]$ which converts $A$ into $ [96,96] $ which is stable.

见题面

见题面