Problem Description

Cristobal has an array of $N$ (possibly negative) integers. The i-th integer in his array is $A_i$. A contiguous non-empty subarray of Cristobal's array is perfect if its total sum is a perfect square. A perfect square is a number that is the product of a non-negative integer with itself. For example, the first five perfect squares are $0$, $1$, $4$, $9$ and $16$.

How many subarrays are perfect? Two subarrays are different if they start or end at different indices in the array, even if the subarrays contain the same values in the same order.

Input Format

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. The first line of each test case contains the integer $N$. The second line contains $N$ integers describing Cristobal's array. The i-th integer is $A_i$.

Output Format

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the number of perfect subarrays.

3
3
2 2 6
5
30 30 9 1 30
4
4 0 0 16

Case #1: 1
Case #2: 3
Case #3: 9

Hint

In sample case #1, there is one perfect subarray: [2 2] whose sum is $2^2$.

In sample case #2, there are three perfect subarrays:

• [$9$], whose total sum is $3^2$.
• [$1$], whose total sum is $1^2$.
• [$30\ 30\ 9\ 1\ 30$], whose total sum is $10^2$.

In sample case #3, there are nine perfect subarrays:

• [$4$], whose total sum is $2^2$.
• [$4\ 0$], whose total sum is $2^2$.
• [$4\ 0\ 0$], whose total sum is $2^2$.
• [$0$], whose total sum is $0^2$.
• [$0\ 0$], whose total sum is $0^2$.
• [$0\ 0\ 16$], whose total sum is $4^2$.
• [$0$], whose total sum is $0^2$.
• [$0\ 16$], whose total sum is $4^2$.
• [$16$], whose total sum is $4^2$.

Note: We do not recommend using interpreted/slower languages for the test set 2 of this problem.

Limits

$1 \le T \le 100$.

$-100 \le A_i \le 100$, for all $i$.

Test Set 1

$1 \le N \le 1000$.

Test Set 2

For up to $5$ cases, $1 \le N \le 10^5$.

For the remaining cases, $1 \le N \le 1000$.