You and your friend Daneliya Tuleshova are planning to hijack a train. Your friend will go inside a cabin and she will throw valuable things through the windows. Your task is to collect it. But there are lots of things inside the cabin so she is throwing whatever she finds. There are different kinds of things in the cabin and they have different values in the market. However, you can't just only pick valuable things. You must collect items consecutively so that the product of their market values becomes maximum. There can't be any unpicked item between any two picked items.
Input
Input starts with a single integer T (1 ≤ T ≤ 100000) denoting the number of test cases. For every test case, there will be a positive integer N (1 ≤ N ≤ 60) denoting the number of things are thrown by Daneliya Tuleshova. Next line there will be N numbers a (-2 ≤ a1, a2, a3, ..........., aN ≤ 2) denotes the value of the things.
Output
Print the case number and the maximum contiguous subarray product. See the format in the sample test case.
Sample
| Input | Output |
|---|---|
1 5 -2 -2 -1 0 2 | Case 1: 4 |
