e-olymp
Problems

Tin Man and the Gummi Bears

Tin Man and the Gummi Bears

prb3409Oneof the most popularInternet resourceswith enviable regularityisan invasionof evilGummiBears.Once on theresource,astheybeginateamleaderto vote"for"(+) or "against"(-) of allmessagesin a row.Realizingthat theiranticscan be found, and they arepunished,GummiBearsin the resourcemasked.To this end, each pair ofGummiBearscreatesa virtual userand attachesitto theavatarof good-naturedteddy bear, so thatall usersfeel thatGummiBearsdo notvote, andteddy bears.

In variouscommunicationsportalresidentsmay votedifferently, but in onereportthe views of allvotersequally.

Tin Man, beingaccustomedto a certainorder,decided to punishmischievous.For thishe needsto startto determine whatthe maximumnumber ofclicksGummiBearswasobservedin thetime toshare.Help himin this.

Input

The firstline containsan integert - number oftest cases, not exceeding100.Next is arow2t, wherefirst inthe first rowshows the numberof activeposts in theobserved periodn (1n105), andthe next line- the ratingcorresponding messageri (ri|2·109|) at the time ofviewing.

Output

For eachtest caseoutputon a linecorresponding tothe solutionin the format specifiedin the exampleoutput.

Time limit 10 seconds
Memory limit 64 MiB
Input example #1
2
2
3 4
5
-7 6 12 -13 9
Output example #1
Case 1: 3
Case 2: 4
Author Анатолий Присяжнюк