/*
鑰冭檻涓ょ涓嶅悓鐨?dp銆?

dp1[i][j]  绾㈣壊鍒?i 钃濊壊鍒?j 
*/
#include<bits/stdc++.h>
using namespace std;

int n;
int a[2*114514];
int dp[2024][2024];
int dp2[2*114514][12];//鍓嶄竴鍒?i 鍚庝竴浣嶇殑棰滆壊 j 
int ans=0;
void solve2(){
	ans=0;
	for(int i=0;i<=n;i++){
		for(int j=0;j<=10;j++){
			dp2[i][j]=INT_MIN;
		}
	}
	dp2[0][0]=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=10;j++){
			dp2[i][j]=dp2[i-1][j]+(a[i]==a[i-1])*a[i];
			ans=max(ans,dp2[i][j]);
		}
		for(int j=0;j<=10;j++){
			dp2[i][a[i-1]]=max(dp2[i][a[i-1]],dp2[i-1][j]+(a[i]==j)*a[i]);
			ans=max(ans,dp2[i][a[i-1]]); 
		}
//		for(int j=0;j<=10;j++){
//			cout<<dp2[i][j]<<' ';
//		}
//		cout<<endl;
	}
	cout<<ans<<endl;
}//O(nB^2) 
void solve(){
	ans=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	if(n>2000){
		solve2();
		return;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			dp[i][j]=0;
			if(i==j)	dp[i][j]=0;
			else if(i>j){
				if(i-j>1){
					dp[i][j]=dp[i-1][j]+(a[i]==a[i-1])*a[i];
				} 
				else{
					for(int k=1;k<=i-2;k++){
						dp[i][j]=max(dp[i][j],dp[k][j]+(a[i]==a[k])*a[i]);
					}
				}
			}
			else{
				if(j-i>1){
					dp[i][j]=dp[i][j-1]+(a[j]==a[j-1])*a[j];
				}
				else{
					for(int k=1;k<=j-2;k++){
						dp[i][j]=max(dp[i][j],dp[i][k]+(a[j]==a[k])*a[j]);
					}
				}
			}
			ans=max(ans,dp[i][j]);
		} 
	}
	cout<<ans<<endl;
	return;
}
int main(){
//	freopen("color.in","r",stdin);
//	freopen("color.out","w",stdout);
	int T;
	cin>>T;
	while(T--)	solve();
	return 0;
}
//涔熻鍦ㄤ笉鍚岀殑鏃剁┖ 杩樼壍鐫€ 浣犵殑鎵? 

赛时代码。

思路是 $dp_{i,j}$ 用 $i$ 和 $j$ 表示两个颜色的最后一个位置，对应测试点 $1\sim10$，$dp2_{i,j}$ 表示后面那一个数列走到 $i$，$j$ 是另一个颜色的最后一个数的值。

交上去 $20$ 分（AC #5 #7 #8 #10，其余全 WA）。求 debug。

如果不是因为这里写挂了我会有 $65$，总分 $205$。