First of all, I want to introduce a method of compressing the array to you. For an array A, we can compress it into the following form: (c₁, v₁) , (c₂, v₂) , ..., (cm, vm). It means that the value of the first c1 elements of the array A is v₁, the value of the next c₂ elements is v₂, and so on.

For arbitrary i ∈ [1, m − 1], if it satisfies that v_i ≠ v_i+1, we think this compression method is “complete compression”. Otherwise, we think this compression method is “incomplete compression”.

There is an example of “complete compression”:

[100,100,−1,3,4,4] ⇒ (2,100),(1,−1),(1,3),(2,4) 

And there is an example of “incomplete compression”:

[10,10,4,4] ⇒ (2,10),(1,4),(1,4)

You can choose an arbitrary compression method to compress the array A, and the score of this compression method is:

Today, Jelly gets an array A of length N. Jelly will execute the following three steps in order: Firstly, he can replace some (or all of) “−1” in the array to arbitrary integer he wants. Secondly, he can choose an arbitrary compression method to compress the array.
Thirdly, he will calculate the score of this compression method.

Jelly wants to know the highest score that he can get. Jelly is too busy, so he wants you for help.

输入描述:

The first line contains an integer T, where T is the number of test cases. T test cases follow. 
For each test case, the first line contains one integer N, where N is the length of the array A. 
The second line contains N integers A1, A2, ... , AN.  
• 1 ≤ T ≤ 105.
• 1 ≤ N ≤ 105.
• −1≤Ai ≤106.
• the sum of N in all test cases doesn’t exceed 106.

输出描述:

For each test case, print one line containing “Case #x: y”, where x is the test case number (starting from
1) and y is the highest score that Jelly can get.

2
9
0 1 1 0 0 -1 1 1 1
3
1 -1 -1

Case #1: 25
Case #2: 9

备注:

For the first case, there is only one way to get the highest score. Firstly, Jelly replaces −1 to 1. Secondly,
Jelly chooses the “complete compression”. Thirdly, Jelly can get 25 points.