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.util.*;
   import java.lang.*;
   import java.io.*;
                                
            public class d{
            public static void main (String[] args) {                        
              PrintWriter pw=new PrintWriter(System.out);
              Scanner sc=new Scanner(System.in);
              int t=0;
                  t=sc.nextInt();
            for(int i1=0;i1<t;i1++){
                 int n=sc.nextInt();
                 int[] a=new int[n];
                 int[][] b=new int[n][27];
                 int[] c=new int[27];
                   ArrayList<Integer> adj[];
                    adj=new ArrayList[27];
            for(int i=0; i<=26; ++i)
	         adj[i]=new ArrayList<>();  
                  for(int i=0;i<n;i++){
                   a[i]=sc.nextInt();
                   adj[a[i]].add(i);
                   c[a[i]]++;
                   b[i][a[i]]=c[a[i]];
                  }
                  for(int i=1;i<=26;i++)
                       for(int j=1;j<n;j++)
                          if(b[j][i]==0)
                             b[j][i]=b[j-1][i];
                             
                             
                  int max=1,v=0,count=0,count2=0,count3=0,v1=0,v2=0,pos=0,pos1=0,max2=0;
                  int[][] count1=new int[n][n];
                 //////////////////////////////////////////////////////////////////////////// 
                   for(int j1=0;j1<n-1;j1++)           
                         for(int j=j1+1;j<n;j++){
                           for(int k=1;k<=26;k++){
                                count=b[j-1][k]-b[j1][k];
                                max2=Math.max(max2,count);
                                 }
                               count1[j1][j]=max2;
                               max2=0;count=0;
                               
                            }
                  
                  
                  
                  
                 //////////////////////////////////////////////////////////////////////////////// 
                  for(int i=1;i<=26;i++){
                       v=adj[i].size();
                      max=Math.max(max,v);
                      
                       for(int j1=0;j1<adj[i].size()-1;j1++)           
                         for(int j=j1+1;j<adj[i].size();j++){
                             pos=j1;pos1=j;
                             v1=adj[i].get(j1);v2=adj[i].get(j);
                             
                                count=count1[v1][v2];
                                
                                max=Math.max(max,count+2*(Math.min(pos+1,adj[i].size()-pos1)));
                                count=0;
                                 
                               
                               
                            }
                           }
                   
                   
               ///////////////////////////////////////////////////////////////////////////   
                pw.println(max);
                //for(int i=0;i<n-1;i++)
                   // for(int j=i+1;j<n;j++)
                    //   pw.println(i+" "+j+" "+count1[0][1]);
                       
                     }
     
               pw.close();
    	}
    }