Multi-Heads Cup, w skrócie MHC, to światowy konkurs programistyczny stworzony dla uczestników mających wiele, wiele głów. W 2023 roku sędzia główny tego wydarzenia, Little Cyan Fish, rozwiązał trudny problem uwierzytelniania za pomocą wielu rodzajów nawiasów.

To był pierwszy raz, kiedy Little Cyan Fish zobaczył zawodników mających wiele, wiele głów. Tym razem Little Cyan Fish przynosi kolejne zadanie nawiasowe swojemu najlepszemu przyjacielowi, który ma wiele, wiele głów. Little Cyan Fish ma w ręku $n$ rodzajów nawiasów, a każdy rodzaj dzieli się na nawiasy otwierające i nawiasy zamykające. Dla wygody używamy $L^i$ do oznaczenia nawiasu otwierającego $i$-tego rodzaju oraz $R^i$ do oznaczenia nawiasu zamykającego $i$-tego rodzaju.

„Hej, nie zapomnij” — pomyślał Little Cyan Fish — „Już wcześniej wyjaśniłem ci, czym jest poprawny ciąg nawiasowy!”. Aby upewnić się, że rozumiesz pojęcie poprawnego ciągu nawiasowego, Little Cyan Fish przygotował następującą formalną definicję poprawnego ciągu nawiasowego:

• $\varepsilon$ (pusty napis) jest poprawnym ciągiem nawiasowym.
• Jeśli $A$ jest poprawnym ciągiem nawiasowym, to $(A)$ również jest poprawnym ciągiem nawiasowym.
• Jeśli $A$ i $B$ są poprawnymi ciągami nawiasowymi, to $AB$ również jest poprawnym ciągiem nawiasowym.

Na przykład „()”, „()()” i „(())” są poprawnymi ciągami nawiasowymi, ale „)(”, „(” i „))” nie są.

Teraz Little Cyan Fish daje ci ciąg nawiasowy $S$ o długości $n$, zawierający $n$ rodzajów nawiasów. Niestety Little Cyan Fish zapomniał rodzajów nawiasów na niektórych pozycjach, a także zapomniał kierunków nawiasów na tych pozycjach. Wspomnienie tych pozycji stało się rozmyte i zostało oznaczone przez Little Cyan Fish znakiem ?.

Little Cyan Fish jest bardzo ciekawy, dla wszystkich $1 \le l \le r \le n$, ile par $(l, r)$ odpowiada podciągom spójnym $S[l \dots r]$ takim, że istnieje sposób wypełnienia znaków ? pewnym rodzajem nawiasu w pewnym kierunku tak, aby dla każdego $1 \le i \le n$ zachodziło:

• Po wyodrębnieniu wszystkich nawiasów rodzaju $i$ (tj. wszystkich $L^i$ oraz $R^i$), otrzymany ciąg nawiasowy (zawierający wyłącznie nawiasy $i$-tego rodzaju) jest poprawnym ciągiem nawiasowym.

Na przykład, jeśli użyjemy „()” do oznaczenia pierwszego rodzaju nawiasów i „[]” do oznaczenia drugiego rodzaju nawiasów, to napis nawiasowy ([?) spełnia powyższy warunek, ponieważ możemy zastąpić ? znakiem ]. Napis (?)] również spełnia powyższy warunek, ponieważ możemy zastąpić ? znakiem [.

Little Cyan Fish chce, abyś obliczył liczbę wszystkich poprawnych par $(l, r)$.

Wejście

Wejście składa się z wielu przypadków testowych. Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $T$ ($1 \le T$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego pierwszy wiersz wejścia zawiera liczbę całkowitą $n$ ($1 \le n \le 2 \times 10^5$), oznaczającą długość napisu nawiasowego.

Kolejny wiersz zawiera $n$ liczb całkowitych $x_1, x_2, \dots, x_n$ ($-n \le x_i \le n$). Te $n$ liczb całkowitych opisuje informacje o napisie nawiasowym, gdzie:

• Jeśli $x_i > 0$, to $i$-ta pozycja reprezentuje nawias otwierający rodzaju $x_i$ (tj. $L^{x_i}$).
• Jeśli $x_i < 0$, to $i$-ta pozycja reprezentuje nawias zamykający rodzaju $-x_i$ (tj. $R^{-x_i}$).
• Jeśli $x_i = 0$, oznacza to, że Little Cyan Fish zapomniał informacji na tej pozycji (tj. ?).

Gwarantuje się, że suma $n$ po wszystkich przypadkach testowych nie przekracza $2 \times 10^5$.

Wyjście

Dla każdego przypadku testowego wypisz jeden wiersz zawierający jedną liczbę całkowitą, oznaczającą odpowiedź.

Przykład

Wejście 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

Wyjście 1

1
3
3
14