Sticks

Time Limit: 3 Seconds    Memory Limit: 32768 KB

Elistaniel is a very happy elf! He has found 4096 magic sticks! He has put them on the ground in one row so that every stick is parallel to each other. But there is one problem with magic sticks: In each second one of the sticks changes its state, which means that a parallel stick becomes normal and a normal stick becomes parallel (so the stick turns by 90 degrees).

TASK

Your task is to tell Elistaniel length of the longest sequence of sticks forming one line (sticks that have changed their state odd number of times) that occured during the observation time.

 

Input

The firs line of input contains number t (1<=t<=20) - the number of test cases. Each test case begins with a single number n - meaning for how long Elistaniel has been watching the sticks. Then n lines follow. Number j in the i-th of the following lines means that in i-th second the j-th stick changed it state.

Output

For each of test cases your program should write one number - length of the longest sequence of sticks forming a line.

Sample Input

1
6
1
3
5
2
4
3

Sample Output

5
Submit

Source: 3MG_Contest