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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.HashMap;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.TreeSet;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author bhavy seth
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE2 solver = new TaskE2();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE2 {
        public int getMaxInRange(int l, int r, TreeSet<Integer> set[], HashMap<Integer, Integer> map[]) {
            //l r inclusive
            int max = 0;
            for (int i = 1; i < 201; i++) {
                int le = -1, ri = -1, lefre = 0, rightfreq = 0;
                if (set[i].floor(r) != null) {
                    if (set[i].floor(l - 1) == null)
                        lefre = 0;
                    else {
                        le = set[i].floor((l - 1));
                        lefre = map[le].get(i);
                    }
                    ri = set[i].floor(r);

                    int freq = map[ri].get(i) - lefre;
                    max = Math.max(freq, max);
                }

            }
            return max;
        }

        public void solve(int testNumber, InputReader sc, PrintWriter out) {
            int t = sc.nextInt();
            while (t-- > 0) {
                int n = sc.nextInt();
                int a[] = new int[n];
                int b[] = new int[201];
                TreeSet<Integer> set[] = new TreeSet[201];
                int maxlen = 0;
                for (int i = 1; i <= 200; i++) {
                    set[i] = new TreeSet<>();
                }
                ArrayList<Integer> list[] = new ArrayList[201];
                for (int i = 1; i <= 200; i++) {
                    list[i] = new ArrayList<>();
                }
                for (int i = 0; i < n; i++) {
                    a[i] = sc.nextInt();
                    set[a[i]].add(i);
                    list[a[i]].add(i);
                    maxlen = Math.max(maxlen, list[a[i]].size());
                }
                HashMap<Integer, Integer> map[] = new HashMap[n];
                for (int i = 0; i < n; i++) {
                    map[i] = new HashMap<>();
                }
                for (int i = 0; i < n; i++) {
                    map[i].put(a[i], b[a[i]] + 1);
                    b[a[i]]++;
                }

                for (int i = 1; i < 201; i++) {
                    for (int j = 0; j < list[i].size() / 2; j++) {
                        int l = list[i].get(j) + 1;
                        int ri = list[i].get(list[i].size() - j - 1) - 1;
                        int maxfreq = getMaxInRange(l, ri, set, map);
                        // out.println("max freq "+maxfreq);
                        maxlen = Math.max(maxlen, (maxfreq + ((j * 2) + 2)));
                    }
                }
                out.println(maxlen);

            }
        }

    }

    static class InputReader {
        BufferedReader br;
        StringTokenizer st;

        public InputReader(InputStream inputStream) {
            br = new BufferedReader(new
                    InputStreamReader(inputStream));
        }

        public String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}

