After confronting Pinocchio, Lampwick decided to further analyse his diary about Pinocchio. (You can find the details about the diary in Part 1 of this problem)
Now he needs to find out the maximum number of days that passed by in which Pinocchio surely didn't lie. Can you help him out?

Input
First line of input contains T, the number of test cases.
For each of the next T lines, two lines follow. The first line contains an integer N, denoting the number of days. The second line contains N space-separated integers L1, L2, ..., LN representing the length of Pinocchio's nose on different days.

Output
For each test case, output contains an integer representing the maximum number of days that went by between which Pinocchio surely didn't lie.

Constraints

1 <= T <= 100
1 <= N <= 10^5
1 <= Li <= 5*10^6

Example
Input:
1
7
1 2 2 3 4 5 5
Output:
1

Explanation
For the example given above, Pinocchio did not lie on day 3rd and 7th, making the maximum number of days that passed by when Pinocchio did not lie in between as 1.

见题面

见题面