행복한 부분배열

배열 $B$에서 인덱스 $L$부터 $R$까지의 부분배열 합을 $F(B, L, R)$라고 정의한다. 양 끝 인덱스를 포함한다. 식으로 쓰면 $F(B, L, R) = B_L + B_{L+1} + \cdots + B_R$이다.

길이가 $K$인 배열 $C$의 모든 접두사 합이 0 이상이면 $C$를 행복한 배열이라고 한다. 즉 $F(C, 1, 1), F(C, 1, 2), \dots, F(C, 1, K)$가 모두 0 이상이다.

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

첫 줄에 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 배열 $\mathbf{A}$의 길이 $N$이 주어지고, 둘째 줄에는 정수 $A_1, A_2, \dots, A_N$이 주어진다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 주어진 배열의 모든 행복한 부분배열 값의 합이다.

• $1 \le T \le 100$
• 모든 $i$에 대해 $-800 \le A_i \le 800$