Sharmeen loves to play with Array. One day she created an array and wonder what will be the max length of a subarray (the whole array is also considered as a subarray) if difference of all the adjacent values in it are zero (0).

Can you help her to find the length of the Max Subarray?

Input

First line contains the number of test cases t (1 <= t <= 50)

For each test case,

In the first line given the size of the array, n (1 <= n <= 10^5) . In the next line given n integers, all the values in this array are in between ( -10^18 to 10^18 ).

Output

For each test case output one line, the size of the Max Subarray.

For clarification see the sample input output.

Example

Input:
1
5
1 1 1 2 2

Output:
3