解题思路

给定长度为 n 的数组 $a$。把所有相邻的三个数形成的三元组 $(a_i,a_{i+1},a_{i+2})$ 记下来，共有 $m=n-2$ 个。题目要求统计三元组对 $(\mathbf{b},\mathbf{c})$ 中，恰好有且只有一个位置不同（海明距离为 1）的对数。

观察：一对三元组只在第 1 位不同 ⇔ 它们的 $(b_2,b_3)$ 完全相同、但 $b_1$ 不同。于是可以把问题拆成三类并求和（互不重叠）：

1. 只在第 1 位不同；
2. 只在第 2 位不同；
3. 只在第 3 位不同。

题目内容

小 Q 得到了一个包含 $n$ 个整数的数组 $a$ 。他非常喜欢三元组，所以他把所有相邻的三个位置都看成一个三元组，然后抄到了他的本子上，一共写了 $n-2$ 个三元组。

当且仅当两个三元组恰好有一个位置不同时，小 $Q$ 认为这两个三元组蕴含了韵律的美。即满足以下条件之一时，小 Q 认为一对三元组符合他的要求：

• $b_1≠c_1$ 且 $b_2=c_2$ 且 $b_3=c_3$ ;

• $b_1=c_1$ 且 $b_2≠c_2$ 且 $b_3=c_3$ ；

• $b_1=c_1$ 且 $b_2=c_2$ 且 $b_3≠c_3$ 。

找出所有他写在本子上的三元组中，符合他的要求的三元组对的数量。

输入描述

单个数据包含多组测试用例

第一行包含一个整数 $t(1≤t≤10^4)$ 测试用例的数量。

对于每组数据：

第一行包含一个整数 $n(3≤n≤2*10^5)$ 表示数组 $a$ 的长度。

第二行包含 $n$ 个整数 $a_1,a_2,a_n(1≤a_i≤10^9)$ 表示数组的元素。

输出描述

对于每个测试用例，输出一个整数，表示符合小 Q 要求的三元组对的数量。

注意，答案可能无法用 $32$ 位数据类型表示。

样例1

输入

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

输出

2
0
2