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