B. Singularity
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a_1, a_2, \ldots, a_n$$$ of positive integers.

You can perform the following operation any number of times:

  • Select a subarray $$$a_l, a_{l+1}, \ldots, a_r$$$ ($$$1 \le l \le r \le n$$$), let $$$k$$$ be the number of distinct elements among $$$a_l, a_{l+1}, \ldots, a_r$$$, and replace every element of that subarray by $$$k$$$ (that is, set $$$a_l = a_{l+1} = \cdots = a_r = k$$$).

Find the minimum number of operations needed to make every element of the array equal to $$$1$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the array.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each test case, output a single integer — the minimum number of operations needed to make all elements equal to $$$1$$$.

Example
Input
2
7
1 1 3 1 2 2 1
1
1
Output
2
0
Note

In the first test case,

  • Select the subarray $$$[3]$$$ ($$$1$$$ distinct value), the array becomes $$$[1, 1, 1, 1, 2, 2, 1]$$$;
  • Select the subarray $$$[2, 2]$$$ ($$$1$$$ distinct value), the array becomes $$$[1, 1, 1, 1, 1, 1, 1]$$$.

So you can make all elements equal to $$$1$$$ in $$$2$$$ operations.