
ZOJ Problem Set  2505
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 ith of the following lines means that in ith second the jth 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 OUTPUT 5  Problemsetter: Wojciech "Glonojad" Baranowski (w.baranowski@gmail.com) Source: 3MG_Contest 