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.*;
import java.text.DecimalFormat;

public final class Solution{

    static int function(ArrayList<Integer> list, int a , int b){
         if(list.size()<3){
             return 0;
         }

         int dpa[] = new int[list.size()];
         int dpb[] = new int[list.size()];
          
          int ca=0;
          int cb=0;
        
        for(int i=0;i<list.size();i++){
            if(list.get(i)==a){
                ca++;
            }else{
                cb++;
            }
            dpa[i]=ca;
            dpb[i]=cb;
        }
        // check for b in middle
        int st=1;
        int las=list.size()-1;
        int maxlen=0;
        for(int i=st;i<las;i++){
            for(int j=i;j<las;j++){
                if(dpa[i-1]==dpa[las]-dpa[j]){
                   int val=dpb[j]-dpb[i-1]+(2*dpa[i-1]);
                   maxlen=Math.max(maxlen,val);
                }
            }
        }
        // check for a int mid 
        st=1;
        las=list.size()-1;
          
          for(int i=st;i<las;i++){
              for(int j=i;j<las;j++){
                   if(dpb[i-1]==dpb[las]-dpb[j]){
                   int val=dpa[j]-dpa[i-1]+(2*dpb[i-1]);
                   maxlen=Math.max(maxlen,val);
                }
              }
          }
       
       return maxlen;



    }

  
    
  static void ne(Scanner sc , BufferedWriter op) throws Exception{
          int n=sc.nextInt();
          int[] arr= new int[n];
          for(int i=0;i<n;i++){
              arr[i]=sc.nextInt();

          }
          ArrayList<pair> list= new ArrayList<>();
          for(int i=0;i<=26;i++){
              for(int j=i;j<=26;j++){
               list.add(new pair(i,j));
            //    list.add(new pair(j,i));
              }
          }
          int max=-1;
          for(int i=0;i<list.size();i++){
            int a=list.get(i).xx;    
            int b=list.get(i).yy;
            if(a==b){
                int cc=0;
                for(int j=0;j<n;j++){
                    if(arr[j]==a){
                        cc++;
                    }
                }
                max=Math.max(cc,max);
            }else{
                
               ArrayList<Integer> ll= new ArrayList<>();
               for(int j=0;j<n;j++){
               if(arr[j]==a || arr[j]==b){
                   ll.add(arr[j]);
                 }
                }
               int len= function(ll,a,b);
               max = Math.max(len,max);
            }
            

          }
          op.write(max+"\n");
  }

 

   public static void main (String[] args) throws Exception
   {  
        BufferedWriter op = new BufferedWriter(new OutputStreamWriter(System.out));
        Scanner sc = new Scanner(System.in);
         
        int t=sc.nextInt();
        while(t-->0) {
            ne(sc,op);
            op.flush();
        }
   }

 }
 
 class pair{
     int xx;

     int yy;
     pair(int xx, int yy){
         this.xx=xx;
         this.yy=yy;
     }
 }

  



 class debug{
         
    
   static void print1d(long [] arr){
       System.out.println();
       for(int i=0;i<arr.length;i++){
           System.out.print(arr[i]+" ");
       }
      
   }
     static void print1d(int [] arr){
       System.out.println();
       for(int i=0;i<arr.length;i++){
           System.out.print(arr[i]+" ");
       }
      
   }
   
    static void print2d(int[][] arr){
        System.out.println();
        int n=arr.length;
        int n2=arr[0].length;
        for(int i=0;i<n;i++){
            for(int j=0;j<n2;j++){
                System.out.print(arr[i][j]+" ");
            }
            System.out.println();
        }
      
    }
     static void print2d(long[][] arr){
        System.out.println();
        int n=arr.length;
        int n2=arr[0].length;
        for(int i=0;i<n;i++){
            for(int j=0;j<n2;j++){
                System.out.print(arr[i][j]+" ");
            }
            System.out.println();
        }
       
    }



 }
  


  

 
 class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;
 
        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(
                new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public String readLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n') {
                    if (cnt != 0) {
                        break;
                    }
                    else {
                        continue;
                    }
                }
                buf[cnt++] = (byte)c;
            }
            return new String(buf, 0, cnt);
        }
 
        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ') {
                c = read();
            }
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
 
            if (neg)
                return -ret;
            return ret;
        }
 
        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }
 
        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
 
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
 
            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }
 
            if (neg)
                return -ret;
            return ret;
        }
 
        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0,
                                 BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }
 
        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }
 
        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
    }

    

//   BufferedWriter op = new BufferedWriter(new OutputStreamWriter(System.out));


// in comparator to sort in in order return -1 
// in comparator to sort in increasing order return 1


// sorting in increasing 
// class Comp implements Comparator<pair>{
//     public int compare(pair a,pair b){
//         if(a.b>b.b){
//             return 1;    here
//         }
//         return -1;
//     }
// }  



