Description:
Polycarp was given an array $$$a$$$ of $$$n$$$ integers. He really likes triples of numbers, so for each $$$j$$$ ($$$1 \le j \le n - 2$$$) he wrote down a triple of elements $$$[a_j, a_{j + 1}, a_{j + 2}]$$$.
Polycarp considers a pair of triples $$$b$$$ and $$$c$$$ beautiful if they differ in exactly one position, that is, one of the following conditions is satisfied:
- $$$b_1 \ne c_1$$$ and $$$b_2 = c_2$$$ and $$$b_3 = c_3$$$;
- $$$b_1 = c_1$$$ and $$$b_2 \ne c_2$$$ and $$$b_3 = c_3$$$;
- $$$b_1 = c_1$$$ and $$$b_2 = c_2$$$ and $$$b_3 \ne c_3$$$.
Find the number of beautiful pairs of triples among the written triples $$$[a_j, a_{j + 1}, a_{j + 2}]$$$.
Input Format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.
The first line of each test case contains a single integer $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — the length of the array $$$a$$$.
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — the elements of the array.
It is guaranteed that the sum of the values of $$$n$$$ for all test cases in the test does not exceed $$$2 \cdot 10^5$$$.
Output Format:
For each test case, output a single integer — the number of beautiful pairs of triples among the pairs of the form $$$[a_j, a_{j + 1}, a_{j + 2}]$$$.
Note that the answer may not fit into 32-bit data types.
Note:
In the first example, $$$a = [3, 2, 2, 2, 3]$$$, Polycarp will write the following triples:
1. $$$[3, 2, 2]$$$;
2. $$$[2, 2, 2]$$$;
3. $$$[2, 2, 3]$$$.
In the third example, $$$a = [1, 2, 3, 2, 2, 3, 4, 2]$$$, Polycarp will write the following triples:
1. $$$[1, 2, 3]$$$;
2. $$$[2, 3, 2]$$$;
3. $$$[3, 2, 2]$$$;
4. $$$[2, 2, 3]$$$;
5. $$$[2, 3, 4]$$$;
6. $$$[3, 4, 2]$$$;