给定一个包含 $n$ 个正整数的序列 $[a_1, \dots, a_n]$。你可以对该序列执行以下操作：

• 选择一个子数组 $a[l \dots r]$ ($1 \le l < r \le n$)，使得其中的元素不全相同（即存在两个整数 $l \le i < j \le r$ 满足 $a_i \neq a_j$），然后将该子数组中的每个元素都变为 $\max_{l \le i \le r} a_i$。

确定可以执行此类操作的最大次数。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 1000$)。接下来是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 2 \times 10^5$)。

每个测试用例的第二行包含 $n$ 个整数 $a_1, \dots, a_n$ ($1 \le a_i \le 10^9$)。

所有测试用例的 $n$ 之和不超过 $4 \times 10^5$。

输出格式

对于每个测试用例，打印可以执行的最大操作次数。

样例

输入 1

4
2
1 2
2
2 2
7
1 1 1 2 2 2 2
3
1 2 3

输出 1

1
0
3
3

说明

在第一个测试用例中，一种最优的操作序列为：

1. 选择 $a[1 \dots 2]$ 并执行操作，使得 $a$ 变为 $[2, 2]$。

在第二个测试用例中，无法执行任何操作。

在第四个测试用例中，一种最优的操作序列为：

1. 选择 $a[1 \dots 2]$ 并执行操作，使得 $a$ 变为 $[2, 2, 3]$。
2. 选择 $a[2 \dots 3]$ 并执行操作，使得 $a$ 变为 $[2, 3, 3]$。
3. 选择 $a[1 \dots 3]$ 并执行操作，使得 $a$ 变为 $[3, 3, 3]$。