Tin Man and the Gummi Bears#3409
One of the most popular Internet resources with enviable regularity is an invasion of evil Gummi Bears. Once on the resource, they all begin to vote on command of their leader "for" () or "against" () on 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 think that it is not Gummi Bears voting, but teddy bears.
Users of the portal may vote differently on different messages, but on a single message the opinion of all voters is the same.
Tin Man, being accustomed to a certain order, decided to punish the mischievous bears. For this he needs to start to determine the maximum number of Gummi Bears that were observed in the clique at the time on the resource. Help him in this.
The first line contains an integer - number of test cases, not exceeding . Next are rows, where the first row of each test case shows the number of active posts in the observed period (1 \le n \le 10^5), and the next row contains the rating of the corresponding message r_i (|r_i| \le 2 \cdot 10^9) at the time of viewing.
For each test case output on a line corresponding to the solution in the format specified in the example output.
Example 1