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.HashSet;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;

 
 
public class C{
	
	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 class Pair
	{
		long o;
		long z;
		Pair(long o,long z)
		{
			this.o = o;
			this.z = z;
		}
	}
	
	static class Node
	{
		Node l;
		Node r;
		char ch;
		Node(char ch)
		{	
			this.ch = ch;
		}
	}
	static int gcd(int a,int b)
	{
		if(a == 0) return b;
		if(b == 0) return a;
		
		return gcd(b,a%b);
	}
	static long gcd(long a,long b)
	{
		if(a == 0) return b;
		if(b == 0) return a;
		
		return gcd(b,a%b);
	}
	static void preCompute(long fact[])
	{
		fact[0] = 1;
		for(int i = 1; i < fact.length; i++)
		{
			fact[i] = i*fact[i-1]%rem;
		}
	}
	static long power(long x, long y, long p) 
    { 
        long res = 1; 
        x = x % p; 
                      
        while (y > 0) 
        {
            if (y % 2 == 1) 
                res = (res * x) % p; 
 
            y = y >> 1; 
            x = (x * x) % p; 
        }
        return res; 
    } 
	static long modInverse(long n, long p) 
    { 
        return power(n, p-2, p); 
    }
	
	static long nCrModPFermat(int n, int r, long p) 
	{ 
 
		if (r == 0) 
			return 1; 
 
		return (fact[n]* modInverse(fact[r], p) % p * modInverse(fact[n-r], p) % p) % p; 
	}
	static long rem = 998244353L;
	static long fact[];
	
	static ArrayList<Integer> ar = new ArrayList<>();
	static void sieve(int n)
	{	
		//System.out.println(n);
		boolean prime[] = new boolean[n+1];
		for(int i=0;i<= n;i++) 
			prime[i] = true; 
      
		for(int p = 2; p*p <=n; p++) 
		{	 
        
			if(prime[p] == true) 
			{ 	
				for(int i = p*p; i <= n; i += p) 
					prime[i] = false; 
			} 
		} 
		
		for(int i = 2; i <= n; i++)
		{
			if(prime[i]) ar.add(i);
		}
	}
	
	
	static long mod = (long)(1e9)+7;
	public static void main(String[] args) 
	{
		OutputStream outputStream = System.out;
		FastReader sc = new FastReader();
        PrintWriter out = new PrintWriter(outputStream);
        
        int t = sc.nextInt();
        
        
        while(t-- > 0)
        {
        	int n = sc.nextInt();

        	int a[] = new int[n];
        	
        	int fmap[][] = new int[n][27];
        	int rmap[][] = new int[n][27];
        	int max = 0;
        	for(int i = 0; i < n; i++)
        	{
        		a[i] = sc.nextInt();
        		if(i == 0)
        		fmap[i][a[i]]++;
        		
        		else
        			{
        			fmap[i][a[i]] += fmap[i-1][a[i]]+1;
        		
        		for(int j = 1; j <= 26; j++)
        		{
        			if(j != a[i])
        			{
        				fmap[i][j] = fmap[i-1][j];
        			}
        		}
        			}
        	}

        	for(int i = n-1; i >= 0; i--)
        	{	
        		if(i == n-1)
        		rmap[i][a[i]]++;
        		
        		else 
        			{
        			rmap[i][a[i]] += rmap[i+1][a[i]]+1;
        			
        		
        		for(int j = 1; j <= 26; j++)
        		{
        			if(j != a[i])
        			{
        				rmap[i][j] = rmap[i+1][j];
        			}
        		}
        			}
        	}
        	
        	int ans = 0;
        	for(int i = 0; i < n; i++)
        	{	
        		int map[] = new int[27];
        		max = 0;
        		for(int j = i+1; j < n; j++)
        		{	
        			int ci = 0;
        			int maxci = 0;
        			for(int k = 1; k <= 26; k++)
        			{
        				ci = Math.min(fmap[i][k],rmap[j][k]);
        				maxci = Math.max(ci,maxci);
        				
        			}
        			//System.out.println(maxci+" "+ans+" "+max+" "+j+" "+i);
    				ans = Math.max(ans,2*maxci+max);
        			map[a[j]]++;
        			max = Math.max(max,map[a[j]]);
        		}
        		
        	}
        	
        	for(int i = 1; i <= 26; i++)
        	{
        		ans = Math.max(ans,fmap[n-1][i]);
        	}
        	out.println(ans);
        }
        out.close();
	}
 
}