给定一个包含 $N$ 个元素的数组 $A = A_1, A_2, \dots, A_N$。

按照以下方式构建一个包含 $N$ 个节点的图 $G$：

• 当且仅当满足以下条件时，连接边 $(i, j)$：
  • $1 \le i < j \le N$
  • 子数组 $A[i, j]$ 存在一个众数（majority element）。

求图 $G$ 的连通分量个数。

子数组 $A[i, j]$ 指的是数组 $[A_i, A_{i+1}, \dots, A_j]$。 长度为 $M$ 的数组 $B$ 存在众数，当且仅当存在某个元素 $X$，其在 $B$ 中出现的次数严格大于 $\frac{M}{2}$。

输入格式

• 第一行包含一个整数 $T$，表示测试用例的数量。
• 每个测试用例包含两行输入：
  • 第一行包含一个整数 $N$，表示数组和图的大小。
  • 第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$。

输出格式

对于每个测试用例，在单独的一行中输出图 $G$ 的连通分量个数。

数据范围

• $1 \le T \le 10^5$
• $2 \le N \le 2 \cdot 10^6$
• $1 \le A_i \le N$
• 所有测试用例的 $N$ 之和不超过 $2 \cdot 10^6$。
• 注意：$N$ 的数据范围比通常情况要大。

样例

样例输入 1

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

样例输出 1

2
4
1
1

说明

测试用例 1：有 2 对 $(i, j)$ 满足众数条件：$(1, 3)$ 和 $(2, 4)$。子数组 $A[1, 3]$ 的众数是 $1$，子数组 $A[2, 4]$ 的众数是 $2$。因此，该图有 2 个连通分量。

测试用例 2：只有一条边 $(2, 4)$。因此，有 4 个连通分量。