Multi-Heads Cup, или сокращённо MHC — это всемирное соревнование по программированию, созданное для участников, у которых много-много голов. В 2023 году главный судья этого соревнования, Little Cyan Fish, решил сложную задачу аутентификации, используя множество типов скобок.

Тогда Little Cyan Fish впервые увидел участников, у которых много-много голов. И на этот раз Little Cyan Fish принёс ещё одну задачу про скобки своему лучшему другу, у которого тоже много-много голов. У Little Cyan Fish в руках $n$ типов скобок, и каждый тип скобок делится на открывающие и закрывающие скобки. Для удобства мы используем $L^i$ для обозначения открывающей скобки $i$-го типа и $R^i$ для обозначения закрывающей скобки $i$-го типа.

«Эй, не забудь, — подумал Little Cyan Fish, — я уже рассказывал тебе раньше, что такое правильная скобочная последовательность!» Чтобы убедиться, что вы понимаете концепцию правильной скобочной последовательности, Little Cyan Fish подготовил следующее формальное определение правильной скобочной последовательности:

• $\varepsilon$ (пустая строка) является правильной скобочной последовательностью.
• Если $A$ — правильная скобочная последовательность, то $(A)$ также является правильной скобочной последовательностью.
• Если $A$ и $B$ — правильные скобочные последовательности, то $AB$ также является правильной скобочной последовательностью.

Например, «()», «()()» и «(())» являются правильными скобочными последовательностями, а «)(», «(» и «))» — нет.

Теперь Little Cyan Fish даёт вам скобочную последовательность $S$ длины $n$, содержащую $n$ типов скобок. К сожалению, Little Cyan Fish забыл типы скобок на некоторых позициях, а также забыл направления скобок на этих позициях. Воспоминания об этих позициях размылись, и Little Cyan Fish обозначил их символом ?.

Little Cyan Fish очень интересно, для всех $1 \le l \le r \le n$, сколько пар $(l, r)$ соответствуют подстрокам $S[l \dots r]$ таким, что существует способ заполнить символы ? некоторым типом скобок в некотором направлении так, чтобы для каждого $1 \le i \le n$ выполнялось следующее:

• Если извлечь все скобки типа $i$ (т. е. все $L^i$ и $R^i$), то полученная скобочная последовательность (содержащая только скобки $i$-го типа) является правильной скобочной последовательностью.

Например, если мы используем «()» для обозначения первого типа скобок и «[]» для обозначения второго типа скобок, то скобочная строка ([?) удовлетворяет указанному выше условию, так как мы можем заменить ? на ]. Строка (?)] также удовлетворяет этому условию, так как мы можем заменить ? на [.

Little Cyan Fish хочет, чтобы вы вычислили количество всех подходящих пар $(l, r)$.

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

Входные данные состоят из нескольких наборов входных данных. Первая строка входных данных содержит одно целое число $T$ ($1 \le T$), обозначающее количество наборов входных данных.

Для каждого набора входных данных первая строка содержит целое число $n$ ($1 \le n \le 2 \times 10^5$), обозначающее длину скобочной строки.

Следующая строка содержит $n$ целых чисел $x_1, x_2, \dots, x_n$ ($-n \le x_i \le n$). Эти $n$ целых чисел описывают информацию о скобочной строке, где:

• Если $x_i > 0$, то $i$-я позиция представляет открывающую скобку $x_i$-го типа (т. е. $L^{x_i}$).
• Если $x_i < 0$, то $i$-я позиция представляет закрывающую скобку $-x_i$-го типа (т. е. $R^{-x_i}$).
• Если $x_i = 0$, это означает, что Little Cyan Fish забыл информацию на этой позиции (т. е. ?).

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

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

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

Пример

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

4
4
1 2 -1 -2
4
1 0 -2 0
6
1 2 3 -3 -2 -1
8
1 0 0 3 0 0 0 -2

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

1
3
3
14