E. Игра с камнями
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Боб решил отдохнуть от домашних заданий по матанализу и придумал для себя игру.

Игра происходит на последовательности куч камней, которая может быть представлена как массив $$$s_1, \ldots, s_k$$$, где $$$s_i$$$ — количество камней в $$$i$$$-й куче. За один ход Боб выбирает две соседние непустые кучи $$$i$$$ и $$$i+1$$$ и убирает по одному камню из каждой. Если куча стала пустой, то её соседи не становятся соседними. Игра заканчивается, когда у Боба нет доступных ходов. Боб считает, что он выиграл, если в конце игры все кучи стали пустыми.

Мы считаем последовательность куч выигрышной, если Боб может начать с неё и выиграть после некоторой последовательности ходов.

Вам дана последовательность $$$a_1, \ldots, a_n$$$, посчитайте количество выигрышных подотрезков $$$a$$$. Другими словами, найдите количество отрезков $$$[l, r]$$$ ($$$1 \leq l \leq r \leq n$$$) таких, что $$$a_l, a_{l+1}, \ldots, a_r$$$ является выигрышной последовательностью куч.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится единственное целое число $$$t$$$ ($$$1 \leq t \leq 3 \cdot 10^5$$$) — количество наборов входных данных. Далее следуют описания наборов входных данных.

Первая строка описания каждого набора входных данных содержит единственное целое число $$$n$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$).

Вторая строка описания каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$).

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

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

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

Пример
Входные данные
6
2
2 2
3
1 2 3
4
1 1 1 1
4
1 2 2 1
4
1 2 1 2
8
1 2 1 2 1 2 1 2
Выходные данные
1
0
4
2
1
3
Примечание

В первом наборе входных данных Боб не может выиграть с подотрезками длины $$$1$$$, так как нет ни одной пары соседних куч для массива длины $$$1$$$.

Во втором наборе входных данных каждый подотрезок не является выигрышным.

В четвертом наборе входных данных подотрезок $$$[1, 4]$$$ выигрышный, потому что Боб может сделать ходы со следующими парами соседних кучек: $$$(2, 3)$$$, $$$(1, 2)$$$, $$$(3, 4)$$$. Другой выигрышный подотрезок это $$$[2, 3]$$$.