如果一个数组 $b_1, b_2, \dots, b_m$ 满足对于任意 $1 \le i \le m - 1$ 都有 $b_i \neq b_{i+1}$，则称该数组为好数组。

给定一个包含 $n$ 个正整数的好数组 $a_1, a_2, a_3, \dots, a_n$。

你可以对该数组执行以下操作： * 选择任意下标 $i$ ($1 \le i \le n$) 和一个数字 $x$ ($1 \le x \le 10^9$)，将 $a_i$ 修改为 $x$。操作后，数组必须仍然是好数组。

你希望执行若干次操作，使得最终数组中恰好包含两个不同的值。确定实现此目标所需的最少操作次数。

输入格式

第一行包含整数 $t$ ($1 \le t \le 10^5$)，表示测试用例的数量。接下来是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 2 \cdot 10^5$)，表示数组的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)，表示数组的元素。保证对于 $1 \le i \le n - 1$ 有 $a_i \neq a_{i+1}$（即数组是好数组）。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示实现数组中恰好有两个不同值所需的最少操作次数。

样例

样例输入 1

2
5
4 5 2 4 5
2
1 2

样例输出 1

3
0

说明

在第一个测试用例中，一种最优的操作序列为： $(4, 5, 2, 4, 5) \to (2, 5, 2, 4, 5) \to (2, 5, 2, 4, 2) \to (2, 5, 2, 5, 2)$。

在第二个测试用例中，数组已经只包含两个不同的值，因此答案为 0。

子任务

1. (20 分)：所有测试用例的 $n$ 之和不超过 100
2. (10 分)：所有测试用例的 $n$ 之和不超过 500
3. (25 分)：所有测试用例的 $n$ 之和不超过 4000
4. (45 分)：无附加限制