多頭盃（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