链接：https://codeforces.ml/contest/1335/problem/D

The only difference between easy and hard versions is constraints.

You are given a sequence aa consisting of nn positive integers.

Let's define a three blocks palindrome as the sequence, consisting of at most two distinct elements (let these elements are aa and bb, aa can be equal bb) and is as follows: [a,a,…,ax,b,b,…,by,a,a,…,ax][a,a,…,a⏟x,b,b,…,b⏟y,a,a,…,a⏟x]. There x,yx,y are integers greater than or equal to 00. For example, sequences [][], [2][2], [1,1][1,1], [1,2,1][1,2,1], [1,2,2,1][1,2,2,1] and [1,1,2,1,1][1,1,2,1,1] are three block palindromes but [1,2,3,2,1][1,2,3,2,1], [1,2,1,2,1][1,2,1,2,1] and [1,2][1,2] are not.

Your task is to choose the maximum by length subsequence of aa that is a three blocks palindrome.

You have to answer tt independent test cases.

Recall that the sequence tt is a a subsequence of the sequence ss if tt can be derived from ss by removing zero or more elements without changing the order of the remaining elements. For example, if s=[1,2,1,3,1,2,1]s=[1,2,1,3,1,2,1], then possible subsequences are: [1,1,1,1][1,1,1,1], [3][3] and [1,2,1,3,1,2,1][1,2,1,3,1,2,1], but not [3,2,3][3,2,3] and [1,1,1,1,2][1,1,1,1,2].

Input

The first line of the input contains one integer tt (1≤t≤20001≤t≤2000) — the number of test cases. Then tt test cases follow.

The first line of the test case contains one integer nn (1≤n≤20001≤n≤2000) — the length of aa. The second line of the test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤261≤ai≤26), where aiai is the ii-th element of aa. Note that the maximum value of aiai can be up to 2626.

It is guaranteed that the sum of nn over all test cases does not exceed 20002000 (∑n≤2000∑n≤2000).

Output

For each test case, print the answer — the maximum possible length of some subsequence of aa that is a three blocks palindrome.

Example

input

Copy

6
8
1 1 2 2 3 2 1 1
3
1 3 3
4
1 10 10 1
1
26
2
2 1
3
1 1 1

output

Copy

7
2
4
1
1
3

代码：

#include<bits/stdc++.h>
using namespace std;
long long t,n,k,max1,s;
long long a[2005],b[2001][30];
map<long long,long long>m[30],p;
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>n;
		max1=0;
		p.clear();
		for(int i=1;i<=26;i++)
		m[i].clear();
		for(int j=1;j<=26;j++)
		b[1][j]=0;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			for(int j=1;j<=26;j++)
			b[i][j]=b[i-1][j];
			b[i][a[i]]++;
			p[a[i]]++;
			m[a[i]][p[a[i]]]=i;
		}
		for(int i=1;i<=26;i++)
		{
			for(int j=1;j<=26;j++)
			{
				if(i==j)
				continue;
				int l,r;
				s=0;
				for(int k=0;;k++)
				{
					l=m[i][1+k];
					r=m[i][p[i]-k];
					if(l>r)
					break;
					if(l==r)
					{
						s=k*2+1;
						max1=max(max1,s);
						break;
					}
					else
					s=b[r][j]-b[l-1][j]+(k+1)*2;
					max1=max(max1,s);
				}
			}
		}
		cout<<max1<<endl;
		
	}
}