The only difference between easy and hard versions is constraints.

You are given a sequence a consisting of n positive integers.

Let's define a three blocks palindrome as the sequence, consisting of at most two distinct elements (let these elements are a and b, a can be equal b) and is as follows: [\underbrace{a, a, ..., a}_{x}, \underbrace{b, b, ..., b}_{y}, \underbrace{a, a, ..., a}_{x}]. There x, y are integers greater than or equal to 0. For example, sequences [], [2], [1, 1], [1, 2, 1], [1, 2, 2, 1] and [1, 1, 2, 1, 1] are three block palindromes but [1, 2, 3, 2, 1], [1, 2, 1, 2, 1] and [1, 2] are not.

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

You have to answer t independent test cases.

Recall that the sequence t is a a subsequence of the sequence s if t can be derived from s 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], then possible subsequences are: [1, 1, 1, 1], [3] and [1, 2, 1, 3, 1, 2, 1], but not [3, 2, 3] and [1, 1, 1, 1, 2].

Input

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

The first line of the test case contains one integer n (1 ≤ n ≤ 2000) — the length of a. The second line of the test case contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 26), where a_i is the i-th element of a. Note that the maximum value of a_i can be up to 26.

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

Output

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

Example

Input


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


7
2
4
1
1
3
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

//import Number_theory.pair;

import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

//import graph_representation.edge;
public class hacker49 {
	public static int r1=0;
	static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
//static 	ArrayList<Integer>[] f=new ArrayList[200001];
static 	int[] deg=new int[100001];
static class y{
	private int a;
	private int b;
	y(int a,int b) {
		this.a=a;
		this.b=b;
	}
}
	static HashMap<Long,Integer> e=new HashMap<>();
	public static void main(String[] args) {
		OutputStream outputStream =System.out;
	    PrintWriter out =new PrintWriter(outputStream);
		FastReader s=new FastReader();
int t=s.nextInt();
while(t>0) {
	int n=s.nextInt();
	int[] a=new int[n+1];
	int g=0;
	int h=0;
	for(int i=1;i<=n;i++)a[i]=s.nextInt();
	ArrayList<y> e=new ArrayList<>();	
	for(int i=1;i<=n;i++) {
//		a[i]=s.nextInt();
		if(i==1) {
			g=1;
			h=a[i];
		}else if(a[i]==h) {
			g++;
		}else {
			e.add(new y(h,g));
			h=a[i];
			g=1;
		}
	}
	e.add(new y(h,g));
	int p=e.size();
	int[][] dp=new int[201][p+1];
	for(int i=1;i<=p;i++) {
		int r=e.get(i-1).a;
		int l=e.get(i-1).b;
		for(int j=1;j<=200;j++) {
			if(j==r) {
				dp[j][i]=dp[j][i-1]+l;
			}else {
				dp[j][i]=dp[j][i-1];
			}
		}
	}
	 ArrayList<Integer>[] f=new ArrayList[201];
	 
	 for(int i=1;i<=200;i++) {
//		 f[e.get(i-1).a].add(i);
		 f[i]=new ArrayList<>();
	 }
	 for(int i=1;i<=p;i++) {
		 f[e.get(i-1).a].add(i);
	 }
	 int ans=0;
for(int k=1;k<=200;k++) {
	for(int i=0;i<f[k].size();i++) {
		for(int j=i;j<f[k].size();j++) {
			int f1=dp[k][f[k].get(j)]-dp[k][f[k].get(i)-1];
			for(int l=1;l<=200;l++) {
				int g1=dp[l][f[k].get(i)-1];
				int g2=dp[l][p]-dp[l][f[k].get(j)];
				ans=Math.max(2*Math.min(g1, g2)+f1, Math.max(ans, dp[k][p]));
			}
		}
	}
}
out.println(ans);
	
	
	t--;
}
out.close();
	}
	public static long GCD(long a,long b) {
		
		if(b==(long)0) {
			return a;
		}
		return GCD(b , a%b);
	}
	static long c=0;
	public static long res=1;
	public static void prime_factorization(long n) {
		for(long i=2;i*i<=n;i++) {
			if(n%i==0) {
				long count=0;
				while(n%i==0) {
					count++;
					n/=i;
				}
//			prime_pairs.add(new pair(i,count));
//			res*=(count+1);
				c+=(count);
			}
		}
		if(n>1) {
//			prime_pairs.add(new pair(n,1));
//		res*=2;
			c+=(1);
		}
		
	}
	static long ans1=0;
	static long ans2=1;
	static long curr=Long.MAX_VALUE;
	static long count3=0;
	static long[] val=new long[100001];
	static HashMap<Long,Long> e5=new HashMap<>();
	static int[] visited=new int[100001];
	static ArrayList<Integer> r2=new ArrayList<>();
	static ArrayList<Integer> SCC=new ArrayList<>();
	public static void kosadfs(int node) {
		visited[node]=1;
		SCC.add(node);
		if(curr>val[node]) {
			count3=1;
			curr=val[node];
		}else if(curr==val[node]){
			count3++;
		}
	
		for(int i=0;i<f1[node].size();i++) {
			if(visited[(int)f1[node].get(i)]==0) {
				kosadfs((int)f1[node].get(i));
			}
		}
	}
	public static void kosarajus_algo(int n) {
		for(int i=1;i<=n;i++) {
			if(visited[i]==0) {
				time(i);
			}
		}
//		time(1);
		for(int i=1;i<=n;i++) {
			visited[i]=0;
		}
		for(int i=n-1;i>=0;i--) {
			if(visited[r2.get(i)]==0) {
				SCC.clear();
				curr=Long.MAX_VALUE;
				count3=0;
				kosadfs(r2.get(i));
				ans1+=curr;
//				count3=0;
				ans2=(ans2*count3)%mod;
				
			}
		}
	}
	public static void time(int v) {
		visited[v]=1;
		for(int i=0;i<f[v].size();i++) {
			if(visited[(int)f[v].get(i)]==0) {
				time((int)f[v].get(i));
			}
		}
		r2.add(v);
	}





	public static int upper_bound(long[] a ,long x,  int g,int n ) {
		int l=g;
		int r=n;
		while(r>l+1) {
			int mid=(l+r)/2;
			if(a[mid]>=x) {
				r=mid;
			}else {
				l=mid;
			}
		}
		return r;
				
	}

//	
//	
	public static int lower_bound(long[] b,long x,int g,int n) {
		int l=g;
		int r=n;
		while(r>l+1) {
			int mid=(l+r)/2;
			if(b[mid]<=x) {
				l=mid;
			}else {
				r=mid;
			}
		}
		return l;
				
	}
	

	static int[] vis1=new int[100001];
	static long count=0;
	static void dfs(int node) {
		vis1[node]=1;
		count++;
		for(int i=0;i<f[node].size();i++) {
			if(vis1[f[node].get(i)]==0)
			dfs(f[node].get(i));
		}
		
	}
	static ArrayList<Integer>[] f=new ArrayList[100001];
	static ArrayList<Integer>[] f1=new ArrayList[100001];
	public static long binary_exponentiation_1(long a,long n) {
		long res=1;
		while(n>0) {
			if(n%2!=0) {
				res=((res)%(1000000007) * (a)%(1000000007))%(1000000007);
				n--;
				
			}else {
				a=((a)%(1000000007) *(a)%(1000000007))%(1000000007);
				n/=2;
			}
		}
		return (res)%(1000000007);
		
	}
	public static long im(long a) {
		return binary_exponentiation_1(a,mod-2)%mod;
	}
	public static long[] fac=new long[10000001];
	public static void find_factorial() {
		fac[0]=1;
		fac[1]=1;
		for(int i=2;i<=200000;i++) {
			fac[i]=(fac[i-1]*i)%(mod);
		}
	}
	static int l=1;
	static int r=1;
	static int[][] vis=new int[301][301];
	static boolean isvalid(int x,int y,int n,int m) {
		if(x>=1 && x<=n && y>=1 && y<=m) {
			return true;
		}
	return false;
	}
static void dfs(int n,int m,int count,int g) {
System.out.print(l+" "+r+" ");
vis[l][r]=1;
if(count==g) {
	return;
}
if(isvalid(l,r+1,n,m) && vis[l][r+1]==0) {
	r++;
	dfs(n,m,count+1,g);
	
}else if(isvalid(l,r-1,n,m) && vis[l][r-1]==0) {
	r--;
	dfs(n,m,count+1,g);
//	l++;
}else {
	l++;
	dfs(n,m,count+1,g);
//	l--;
}

}
	public static long be(long a,long n) {
		long res=1;
		while(n>0) {
			if(n%2!=0) {
				res=((res)%(1000000007) * (a)%(1000000007))%(1000000007);
				n--;
			}else {
				a=((a)%(1000000007) *(a)%(1000000007))%(1000000007);
				n/=2;
			}
		}
		return (res)%(1000000007);
		
	}
//	
	static class pair2 implements Comparable<pair2>{
		private int a;
		private int b;
		private long  c;
		pair2(int a,int b,long c){
			this.a=a;
			this.b=b;
			this.c=c;
		}
		public int compareTo(pair2 o) {
//			
//			return Long.compare(o.c,this.c);
			if(Long.compare(o.c, this.c)!=0) {
				return Long.compare(o.c,this.c);}
			else {
				return Long.compare(deg[this.a]+deg[this.b], deg[o.a]+deg[o.b]);
			}
		}
		
	}
	


		
	
	
	
	public static long[] merge_sort(long[] A, int start, int end) {
		if (end > start) {
			int mid = (end + start) / 2;
			long[] v = merge_sort(A, start, mid);
			long[] o = merge_sort(A, mid + 1, end);
			return (merge(v, o));
		} else {
			long[] y = new long[1];
			y[0] = A[start];
			return y;
		}
	}
	public static long[] merge(long a[], long b[]) {
//		int count=0;
		long[] temp = new long[a.length + b.length];
		int m = a.length;
		int n = b.length;
		int i = 0;
		int j = 0;
		int c = 0;
		while (i < m && j < n) {
			if (a[i] < b[j]) {
				temp[c++] = a[i++];
			
			} else {
				temp[c++] = b[j++];
			}
		}
		while (i < m) {
			temp[c++] = a[i++];
		}
		while (j < n) {
			temp[c++] = b[j++];
		}
		return temp;
	}
	
	public static int[] merge_sort1(int[] A, int start, int end) {
		if (end > start) {
			int mid = (end + start) / 2;
			int[] v = merge_sort1(A, start, mid);
			int[] o = merge_sort1(A, mid + 1, end);
			return (merge1(v, o));
		} else {
			int[] y = new int[1];
			y[0] = A[start];
			return y;
		}
	}
	public static int[] merge1(int a[], int b[]) {
//		int count=0;
		int[] temp = new int[a.length + b.length];
		int m = a.length;
		int n = b.length;
		int i = 0;
		int j = 0;
		int c = 0;
		while (i < m && j < n) {
			if (a[i] < b[j]) {
				temp[c++] = a[i++];
			
			} else {
				temp[c++] = b[j++];
			}
		}
		while (i < m) {
			temp[c++] = a[i++];
		}
		while (j < n) {
			temp[c++] = b[j++];
		}
		return temp;
	}
	
	static long mod=1000000007;
	




//	for(int i=2;i<=100000;i++) {
		
	
}