행복한 부분 배열

$F(B, L, R)$를 배열 $B$에서 인덱스 $L$와 $R$을 양 끝으로 하는 부분 배열의 합으로 정의한다(양 끝 인덱스 모두 포함). 형식적으로, $F(B, L, R) = B_L + B_{L+1} + \cdots + B_R$.

길이가 $K$인 배열 $C$에서 $C$의 모든 접두사 합이 음이 아니면 이 배열을 행복한 배열이라고 한다. 형식적으로, 항 $F(C, 1, 1), F(C, 1, 2), \dots, F(C, 1, K)$은 모두 음이 아니다.

$\mathbf{N}$개의 정수로 이루어진 배열 $\mathbf{A}$가 주어질 때, 배열 $\mathbf{A}$의 모든 행복한 부분 배열의 합을 더한 결과를 구한다.

제한

시간 제한: 25초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. 모든 $i$에 대해 $-800 \le \mathbf{A_i} \le 800$.

테스트 세트 1

$1 \le \mathbf{N} \le 200$.

테스트 세트 2

최대 30개의 경우에 대해: $1 \le \mathbf{N} \le 4 \times 10^5$. 나머지 경우에 대해: $1 \le \mathbf{N} \le 200$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 입력 배열 $\mathbf{A}$에 포함된 정수의 개수를 나타내는 정수 $\mathbf{N}$ 하나로 이루어진 줄로 시작한다. 그다음 줄에는 주어진 입력 배열 $\mathbf{A}$의 정수들을 나타내는 $\mathbf{N}$개의 정수 $\mathbf{A_1}, \mathbf{A_2}, \dots, \mathbf{A_N}$가 주어진다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 주어진 입력 배열 $\mathbf{A}$의 모든 행복한 부분 배열의 합을 더한 결과이다.

예제 케이스 #1에서 행복한 부분 배열은 $[1], [3], [3, -2], [3, -2, 4],$와 $[4]$이며, 각각의 합은 $1, 3, 1, 5,$와 $4$이다. 구한 합들을 더하면 결과는 $14$이다.

예제 케이스 #2에서 행복한 부분 배열은 $[1], [1, 0], [1, 0, 3], [0], [0, 3],$와 $[3]$이며, 각각의 합은 $1, 1, 4, 0, 3,$와 $3$이다. 구한 합들을 더하면 결과는 $12$이다.