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.util.Scanner; 
import java.util.StringTokenizer;
import java.util.*;
public class codeforcesE{
   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 long f1(long[] a, long[] b){
      return a[0]-b[0];
    }
    public static  void Sort(long[][] array, final int columnNumber){
        Arrays.sort(array, new Comparator<long[]>() {
            @Override
            public int compare(long[] first, long[] second) {
               if(first[columnNumber-1] > second[columnNumber-1]) return 1;
               else return -1;
            }
        });
    }
   public static void main(String args[]){
     FastReader sc=new FastReader();
      int t=sc.nextInt();
      StringBuilder sb=new StringBuilder();
      while(t-->0){
           int n=sc.nextInt();
           int ar[]=new int[n];
           int dp[][]=new int[27][n+2];
           for(int i=1;i<=n;i++){
               ar[i-1]=sc.nextInt();dp[ar[i-1]][i]++;
            }
            int ans=1;
            for(int i=1;i<27;i++){
                 for(int j=1;j<=n;j++){
                      dp[i][j]+=dp[i][j-1];
                    }
            }
           for(int p1=1;p1<=n;p1++){
                  //System.out.println(p1+" "+p2+"-->"+ans);
                  for(int p2=p1;p2<=n;p2++){
                  int m=0,s=0;
                  for(int i=0;i<27;i++){
                      s=Math.max(s,Math.min(dp[i][p1-1],dp[i][n]-dp[i][p2])*2);
                    }
                  for(int i=0;i<27;i++){m=Math.max(m,dp[i][p2]-dp[i][p1-1]);}
                  ans=Math.max(ans,m+s);
                }
            }
            System.out.println(ans);
        }
        
    }
}