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$번째 종류의 괄호만 포함)이 올바른 괄호 문자열이다.

예를 들어, "()"로 첫 번째 종류의 괄호를 나타내고 "[]"로 두 번째 종류의 괄호를 나타낸다면, 괄호 문자열 ([?)는 ?를 ]로 바꿀 수 있으므로 위 조건을 만족합니다. (?)] 또한 ?를 [로 바꿀 수 있으므로 위 조건을 만족합니다.

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