Tin Man and the Gummi Bears

Oneof 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 (1 ≤ n ≤ 10⁵), andthe next line- the ratingcorresponding messager_i (r_i ≤ |2·10⁹|) at the time ofviewing.

Output

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