Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Train Hijack

By cosmicray001 · Limits 1s, 512 MB


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

InputOutput
1
5
-2 -2 -1 0 2
Case 1: 4

Discussion

Statistics


70% Solution Ratio

RamprosadGEarliest, 7M ago

prodip_bsmrstuFastest, 0.2s

siam009Lightest, 3.2 MB

theunownShortest, 439B

Submit

Login to submit

Related Contests