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
        ////////////////////////////////////////////////////
        //                                                //
        //  For her who keeps the fire kindling in me...  //
        //                                                //
        ////////////////////////////////////////////////////


        import java.io.BufferedReader;
        import java.io.BufferedWriter;
        import java.io.FileOutputStream;
        import java.io.IOException; 
        import java.io.InputStreamReader;
        import java.io.OutputStream;
        import java.io.OutputStreamWriter;
        import java.io.PrintWriter;
        // import java.util.Scanner;
        // import java.util.Arrays;
        // import java.util.ArrayList;
        // import java.util.Collections; 
        // import java.util.StringTokenizer;
        import java.util.*;
        import java.lang.Math;
        import java.awt.Point;                            
        
        import java.awt.geom.*;
        
        public class Main{
        
            static class Pair{
                int x;
                int y;
            }
        
        
        
        
            static class DisjointUnionSets { 
                int[] rank, parent, ele_count; 
                int n; 
                
                // Constructor 
                public DisjointUnionSets(int n) 
                { 
                    rank = new int[n]; 
                    parent = new int[n];
                    ele_count = new int[n];
                    this.n = n; 
                    makeSet(); 
                } 
                
                // Creates n sets with single item in each 
                void makeSet() 
                { 
                    for (int i = 0; i < n; i++) { 
                        // Initially, all elements are in 
                        // their own set. 
                        parent[i] = i; 
                        ele_count[i] = 1;
                    } 
                } 
                
                // Returns representative of x's set 
                int find(int x) 
                { 
                    // Finds the representative of the set 
                    // that x is an element of 
                    if (parent[x] != x) { 
                        // if x is not the parent of itself 
                        // Then x is not the representative of 
                        // his set,
        
                        parent[x] = find(parent[x]); 
                        
                        // so we recursively call Find on its parent 
                        // and move i's node directly under the 
                        // representative of this set 
                    } 
                
                    return parent[x]; 
                }
        
        
        
                int setSize(int x){
                    int par = find(x);
                    return ele_count[par];
                }
                
        
        
                // Unites the set that includes x and the set 
                // that includes x 
                void union(int x, int y) 
                { 
                    // Find representatives of two sets 
                    int xRoot = find(x), yRoot = find(y); 
                
                    // Elements are in the same set, no need 
                    // to unite anything. 
                    if (xRoot == yRoot) 
                        return; 
                
                    // If x's rank is less than y's rank 
                    if (rank[xRoot] < rank[yRoot]){ 
                
                        // Then move x under y  so that depth 
                        // of tree remains less 
                        parent[xRoot] = yRoot;
                    
                        ele_count[yRoot] = ele_count[yRoot] + ele_count[xRoot];
                
                    // Else if y's rank is less than x's rank 
                    }else if (rank[yRoot] < rank[xRoot]) {
                
                        // Then move y under x so that depth of 
                        // tree remains less 
                        parent[yRoot] = xRoot; 
                        ele_count[xRoot] = ele_count[yRoot] + ele_count[xRoot];
                    
                    } else // if ranks are the same 
                    { 
                        // Then move y under x (doesn't matter 
                        // which one goes where) 
                        parent[yRoot] = xRoot; 
                
                        ele_count[xRoot] = ele_count[yRoot] + ele_count[xRoot];
        
                        // And increment the result tree's 
                        // rank by 1 
                        rank[xRoot] = rank[xRoot] + 1; 
                    } 
                } 
            } 
        
        
            static long power(long x, long y, long p) 
            { 
                // Initialize result 
                long res = 1l;      
                
                // Update x if it is more   
                // than or equal to p 
                x = x % p;  
            
                while (y > 0) 
                { 
                    // If y is odd, multiply x 
                    // with result 
                    if((y & 1)==1) 
                        res = (res * x) % p; 
            
                    // y must be even now 
                    // y = y / 2 
                    y = y >> 1;  
                    x = (x * x) % p;  
                } 
                return res; 
            } 
        
        
        
        static int countGreater(int arr[], int n, int k) 
        { 
        int l = 0; 
        int r = n - 1; 
        
        // Stores the index of the left most element 
        // from the array which is greater than k 
        int leftGreater = n; 
        
        // Finds number of elements greater than k 
        while (l <= r) { 
            int m = l + (r - l) / 2; 
        
            // If mid element is greater than 
            // k update leftGreater and r 
            if (arr[m] > k) { 
                leftGreater = m; 
                r = m - 1; 
            } 
        
            // If mid element is less than 
            // or equal to k update l 
            else
                l = m + 1; 
        } 
        
        // Return the count of elements greater than k 
        return (n - leftGreater); 
        } 
        
        
        
        static int countLessEqual(int arr[], int n, int k) 
        { 
        int l = 0; 
        int r = n - 1; 
        
        // Stores the index of the left most element 
        // from the array which is greater than k 
        int leftGreater = n; 
        
        // Finds number of elements greater than k 
        while (l <= r) { 
            int m = l + (r - l) / 2; 
        
            // If mid element is greater than 
            // k update leftGreater and r 
            if (arr[m] > k) { 
                leftGreater = m; 
                r = m - 1; 
            } 
        
            // If mid element is less than 
            // or equal to k update l 
            else
                l = m + 1; 
        } 
        
        // Return the count of elements greater than k 
        return (leftGreater); 
        } 
        
        
        
            public static void main(String args[]){
                try{
                    FastReader s = new FastReader();
                    BufferedWriter w = new BufferedWriter(new OutputStreamWriter(System.out));
                    int i, q, j, k, x, y, t, n, ind, count, diff, key, l, r, b, size, Pairer, max, sec_max, minglob, minloc, beg, end, begl, endr, ld, up, down, maxele, minele, case_count;
                    long ans, sqrt, sum, maxup, maxdown, m, X, Y, Q, MOD;//, sum2;
                    boolean flag, flag2;
                    boolean l2r;
        
                    double avg;
                    char c, c2;
                    String str;
                
                    t = s.nextInt();
                    for(; t>0; t--){
                    
                        n = s.nextInt();
                    
                        int countarr[][] = new int[27][n+1];
                        int arr[] = new int[n];


                        // Arrays.fill(countarr, 0);

                        for(i=0; i<n; i++){
                            arr[i] = s.nextInt();
                            countarr[arr[i]][i] = 1;
                        }

                        
                        for(j=1; j<=26; j++)
                            for(i=1; i<n; i++)
                                countarr[j][i] += countarr[j][i-1]; 



                        max = 0; maxele = 0; ans = 1;
                        // int dp[][] = new int[n][n];
                        for(i=0; i<(n); i++){
                            for(j=i; j<(n); j++){
                                max = 0;
                                for(k=1; k<=26; k++){
                                    if( (i!=0)  &&  countarr[k][i-1]  ==  (countarr[k][n-1] - countarr[k][j]))
                                        max = (int)Math.max(max, countarr[k][i-1] + countarr[k][n-1]- countarr[k][j]);
                                }


                                // if(max != 0){
                                    maxele = 0;
                                    for(k=1; k<=26; k++){
                                        if(i!=0)
                                            maxele = (int)Math.max(maxele, countarr[k][j] - countarr[k][i-1]);
                                        else 
                                            maxele = (int)Math.max(maxele, countarr[k][j] );
                                    }
                                // }
                                
                                ans = (long)Math.max(max+maxele, ans);
                            }
                        }
        


                        // max = 0; maxele = 0; ans = 1;
                        // // int dp[][] = new int[n][n];
                        // for(i=1; i<(n-1); i++){
                        //     for(j=i; j<(n-1); j++){
                        //         max = 0;
                        //         for(k=1; k<=26; k++){
                        //             if(countarr[k][i-1]  ==  (countarr[k][n-1] - countarr[k][j]))
                        //                 max = (int)Math.max(max, countarr[k][i-1] + countarr[k][n-1]- countarr[k][j]);
                        //         }


                        //         // if(max != 0){
                        //             maxele = 0;
                        //             for(k=1; k<=26; k++){
                        //                 maxele = (int)Math.max(maxele, countarr[k][j] - countarr[k][i-1]);
                        //             }
                        //         // }
                               
                        //         ans = (long)Math.max(max+maxele, ans);
                        //     }
                        // }



                        // max = 1;
                        // for(i=1; i<(n-1); i++){
                        //     for(j=i; j<(n-1); j++){

                        //         for(k=1; k<=26; k++){
                        //             max = (int)Math.max(max, dp[i][j] + countarr[k][j] - countarr[k][i-1]);
                        //         }
                                
                        //     }
                        // }


                        
                        // for(i=0; i<n; i++){
                            w.write((ans)+"");            
                            w.write("\n");
                        // }
                            
                    }
                    w.close();
                }catch(Exception e){
                    e.printStackTrace();
                }
            }
        }
                        
                        
        //========================================### FAST IO ###=========================================//
        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;
            } 
        }
            //====================================================================================================//
        