Migrated from Lutece 448 Longest Subsequence

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Recently,Nero is researching a kind of sequence problem related to the sphere.This kind of problem ressembles the Longest Ascending Subsequence.

For instance,Given a sequence,can you find the longest subsequence in it?

Following constraints should be meeted:

1. the elements in the subsequence should be totally equal.
2. the interval between the adjacent elements in the subsequence shouldn't be greater than one(in the hint,we'll show clearly what the interval is)

Input

$T$ indicating the number of test cases

Each case begins with a interger $n$($0\leq n\leq 1000$),representing the length of sequence

Following are $n$ integers, $P_i$ stands for the value of each element.

Output

One line,contains a integer indicating the length of the longest subsequence.

Samples

2
6
1 2 2 1 1 1
8
1 2 2 2 1 1 1 1

3
4

Note

In Sample $1$,the interval between the the first $1$ and the second $1$ is $2$.

Resources

5th BUPT Programming Contest Final