\includegraphics{https://static.e-olymp.com/content/26/26480d91577f1301700f5999475e6e640011cce0.jpg} One of the most popular Internet resources with enviable regularity is an invasion of evil Gummi Bears. Once on the resource, as they begin a team leader to vote "for" (\textbf{+}) or "against" (\textbf{-}) of all messages in a row. Realizing that their antics can be found, and they are punished, Gummi Bears in the resource masked. To this end, each pair of Gummi Bears creates a virtual user and attaches it to the avatar of good-natured teddy bear, so that all users feel that Gummi Bears do not vote, and teddy bears. In various communications portal residents may vote differently, but in one report the views of all voters equally. Tin Man, being accustomed to a certain order, decided to punish mischievous. For this he needs to start to determine what the maximum number of clicks Gummi Bears was observed in the time to share. Help him in this. \InputFile The first line contains an integer \textbf{t} - number of test cases, not exceeding \textbf{100}. Next is a row \textbf{2t}, where first in the first row shows the number of active posts in the observed period \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{10^5}), and the next line - the rating corresponding message \textbf{r_i} (\textbf{r_i} ≤ \textbf{|2·10^9}|) at the time of viewing. \OutputFile For each test case output on a line corresponding to the solution in the format specified in the example output.