#216880. [GKS 2022 #G] Happy Subarrays

Let us define as the sum of a subarray of an array bounded by indices and (both inclusive). Formally, .

An array of length is called a happy array if all the prefix sums of are non-negative. Formally, the terms are all non-negative.

Given an array of integers, find the result of adding the sums of all the happy subarrays in the array .

The first line of the input gives the number of test cases, . test cases follow.

Each test case begins with one line consisting an integer denoting the number of integers in the input array . Then the next line contains integers representing the integers in given input array .

For each test case, output one line containing Case #: , where is the test case number (starting from ) and is the result of adding the sums of all happy subarrays in the given input array .

样例输入 1

2
5
1 -2 3 -2 4
3
1 0 3

样例输出 1

Case #1: 14
Case #2: 12

In Sample Case # , the happy subarrays are [], [], [], [], and [] with their respective sums , , , , and . After adding the sums obtained, the result is .

In Sample Case # , the happy subarrays are [], [], [], [], [], and [] with their respective sums , , , , , and . After adding the sums obtained, the result is .

Limits

.

, for all .

Test Set 1

.

Test Set 2

For at most cases:

.

For the remaining cases:

.