C. Неразделённая любовь
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

K1o0n дошёл до той стадии, когда для полного счастья не хватает музыкального инструмента, и купил с рук синтезатор. У инструмента $$$n$$$ клавиш, дающих $$$a_1, a_2, \ldots, a_n$$$ единиц зрительской любви.

Играть по одной ноте скучно, поэтому K1o0n разучил единственный приём — трезвучие: три клавиши через одну, нажатые разом. Трезвучие с началом $$$x$$$ ($$$1 \le x \le n - 4$$$) — это клавиши $$$x$$$, $$$x+2$$$ и $$$x+4$$$, которое приносит $$$a_x + a_{x+2} - a_{x+4}$$$ единиц зрительской любви.

Клавиши старые, и каждая выдерживает ровно одно нажатие. Поэтому K1o0n хочет выбрать ровно два разных трезвучия, которые не имеют общих клавиш. Кроме того, он хочет, чтобы оба трезвучия принесли одинаковое количество зрительской любви.

Посчитайте количество способов выбрать два таких трезвучия.

Входные данные

Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 10^4$$$)  — количество наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$6 \le n \le 2 \cdot 10^5$$$) — количество клавиш.

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_i$$$ ($$$-10^4 \le a_i \le 10^4$$$) — единицы зрительской любви.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора выведите одно целое число — количество неупорядоченных пар непересекающихся трезвучий с равными значениями зрительской любви.

Обратите внимание, что ответ может не поместиться в 32-битный тип данных. Используйте 64-битный тип (long long в C++, long в Java).

Пример
Входные данные
3
6
5 1 4 2 2 -4
7
0 0 0 0 0 0 0
12
-4 3 0 -4 -4 -1 -4 1 -3 -2 -2 -1
Выходные данные
1
2
5
Примечание

В первом наборе данных такая пара единственная: $$$x = 1$$$, $$$y = 2$$$: $$$5 + 4 - 2 = 1 + 2 - (-4)$$$.

Во втором наборе данных таких пар две: $$$x = 1$$$, $$$y = 2$$$ и $$$x = 3$$$, $$$y = 2$$$, каждое трезвучие приносит $$$0$$$ единиц зрительской любви.