题目描述

小红定义一个数组是“双生数组”，当且仅当该数组大小为偶数，数组的元素种类恰好为 $2$ 种，且这两种元素的出现次数相同。例如 $\left\{1,1,4,4,1,4\right\}$ 是双生数组。
现在小红拿到了一个数组，她希望你计算该数组有多少连续子数组是双生数组。
子数组为从原数组中，连续的选择一段元素（可以全选、可以不选）得到的新数组。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1\leq T\leq 10^4\right)$ 代表数据组数，每组测试数据描述如下：
第一行输入一个正整数 $n \left(1 \leq n \leq 10^5\right)$ 代表数组元素数量。
第二行输入 $n$ 个正整数 $a_1,a_2,\dots,a_n$$\left(1 \leq a_i \leq 10^9\right)$ 代表数组元素。

除此之外，保证单个测试文件的 $n$ 之和不超过 $10^5$。

输出描述

$\hspace{15pt}$对于每组测试数据，新起一行。输出一个整数，代表连续子数组是双生数组的数量。

样例1

输入

3
3
1 2 1
4
6 6 6 6
6
1 1 4 4 1 4

输出

2
0
6

说明

对于第三组测试数据，长度为 $2$ 的连续子数组是双生数组的有 $3$ 个，长度为 $4$ 的有 $2$ 个，长度为 $6$ 的有 $1$ 个。