B'Polycarp was given an array a of n integers. He really likes triples of numbers, so for each j ( 1 <= j <= 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: Find the number of beautiful pairs of triples among the written triples [a_j, a_{j + 1}, a_{j + 2}] . The first line contains a single integer t ( 1 <= t <= 10^4 ) -- the number of test cases. The first line of each test case contains a single integer n ( 3 <= n <= 2 cdot 10^5 ) -- the length of the array a . The second line of each test case contains n integers a_1, a_2, ... , a_n ( 1 <= a_i <= 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 . 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. In the first example, a = [3, 2, 2, 2, 3] , Polycarp will write the following triples: In the third example, a = [1, 2, 3, 2, 2, 3, 4, 2] , Polycarp will write the following triples: '...