多頭盃（Multi-Heads Cup，簡稱 MHC）係一項為擁有好多好多個頭嘅參賽者舉辦嘅全球性程式設計競賽。喺 2023 年，呢項賽事嘅總裁判小藍魚（Little Cyan Fish）利用多種唔同類型嘅括號解決咗一個棘手嘅身份驗證問題。

嗰次係小藍魚第一次見到擁有好多好多個頭嘅參賽者。而今次，小藍魚為佢擁有好多好多個頭嘅好朋友帶嚟咗另一個括號問題。小藍魚手頭上有 $n$ 種類型嘅括號，每種類型嘅括號都分為左括號同右括號。為咗方便起見，我哋用 $L^i$ 表示第 $i$ 種類型嘅左括號，用 $R^i$ 表示第 $i$ 種類型嘅右括號。

「喂，唔好唔記得呀，」小藍魚心諗，「我之前向你介紹過咩係合法括號序列㗎！」為咗確保你理解合法括號序列嘅概念，小藍魚準備咗以下關於合法括號序列嘅正式定義：

• $\varepsilon$（空字串）係一個合法括號序列。
• 如果 $A$ 係一個合法括號序列，噉 $(A)$ 都係一個合法括號序列。
• 如果 $A$ 同 $B$ 都係合法括號序列，噉 $AB$ 都係一個合法括號序列。

例如，「()」、「()()」同「(())」係合法括號序列，但「)(」、「(」同「))」唔係。

而家，小藍魚畀你一個長度為 $n$ 嘅括號序列 $S$，入面包含 $n$ 種類型嘅括號。不幸嘅係，小藍魚唔記得咗某啲位置嘅括號類型，亦都唔記得咗呢啲位置嘅括號方向。對呢啲位置嘅記憶已經變得模糊，被小藍魚用 ? 表示。

小藍魚非常好奇，對於所有 $1 \le l \le r \le n$，有幾多個數對 $(l, r)$ 對應嘅子串 $S[l \dots r]$，滿足存在一種用某種方向嘅某種類型括號填補 ? 嘅方案，使得對於每個 $1 \le i \le n$，都滿足：

• 提取出所有第 $i$ 種類型嘅括號（即所有嘅 $L^i$ 同 $R^i$），得到嘅括號序列（只包含第 $i$ 種括號）係一個合法括號序列。

例如，如果我哋用「()」表示第一種括號，用「[]」表示第二種括號，噉括號字串 ([?) 滿足上述條件，因為我哋可以將 ? 替換為 ]。(?)] 都滿足上述條件，因為我哋可以將 ? 替換為 [。

小藍魚想你計算所有合法數對 $(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$，表示小藍魚唔記得咗該位置嘅資訊（即 ?）。

保證所有測試數據嘅 $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