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 は $n$ 種類の括弧を含む長さ $n$ の括弧列 $S$ をあなたに与えます。残念なことに、Little Cyan Fish はいくつかの位置にある括弧の種類を忘れてしまい、さらにそれらの位置にある括弧の向きも忘れてしまいました。これらの位置に関する記憶は曖昧になり、Little Cyan Fish によって ? で表されています。

Little Cyan Fish は、すべての $1 \le l \le r \le n$ について、部分文字列 $S[l \dots r]$ に対応する組 $(l, r)$ のうち、? をある種類の括弧かつある向きで埋める方法が存在して、各 $1 \le i \le n$ について以下を満たすものがいくつあるか非常に気になっています：

• 種類 $i$ のすべての括弧（すなわちすべての $L^i$ と $R^i$）を抽出して得られる括弧列（$i$ 番目の種類の括弧のみを含む）が正しい括弧列である。

例えば、「()」で 1 番目の種類の括弧を表し、「[]」で 2 番目の種類の括弧を表す場合、括弧文字列 ([?) は ? を ] に置き換えることができるため上記の条件を満たします。(?)] も ? を [ に置き換えることができるため上記の条件を満たします。

Little Cyan Fish は、すべての有効な組 $(l, r)$ の個数を求めてほしいと考えています。

入力

複数のテストケースが与えられます。入力の 1 行目には、テストケースの個数を表す単一の整数 $T$ ($1 \le T$) が含まれます。

各テストケースについて、入力の 1 行目には括弧文字列の長さを表す整数 $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 つの整数を含む 1 行を出力してください。

出力例

入力 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