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.io.*;

public class Main {
  // Re-implemeting tourist solution
  public static void main(String[] args) throws Exception {

    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter out = new PrintWriter(System.out);

    int TT = Integer.parseInt(in.readLine());
    int currTT = 0;
    StringBuilder output = new StringBuilder();

    int M = 200;
    while (currTT++ < TT) {
      int n = Integer.parseInt(in.readLine());
      int[] a = new int[n];

      String[] input = in.readLine().split("\\s+");
      for (int i = 0; i < n; i++) {
        a[i] = Integer.parseInt(input[i]);
      }

      // store num of occurence of each element 1 <= x <= M at every index i <= n in occ
      // store indices of each occurence in occIndex
      int[][] occ = new int[M + 1][n + 1];
      ArrayList<ArrayList<Integer>> occIndices = new ArrayList<ArrayList<Integer>>();
      // ai does not evaluate to 0
      occIndices.add(new ArrayList<Integer>());

      for (int x = 1; x <= M; x++) {
        ArrayList<Integer> xOccIndices = new ArrayList<Integer>();

        for (int i = 0; i < n; i++) {
          if (a[i] == x) {
            occ[x][i + 1] = occ[x][i] + 1;
            xOccIndices.add(i);
          } else {
            occ[x][i + 1] = occ[x][i];
          }
        }

        occIndices.add(xOccIndices);
      }

      int max = 1;
      // for each element 1 <= x <= M
      // check if it occurs more than current max (to handle odd cases)
      // try the half of its occurences (1st occ with last, 1st and 2nd with last and 2nd to last....)
      // get the indices range of each possibility
      // try all other elements xx, to find ones that fit into the range of current possibility
      // update ans with the number of used occurences and the number of occurences of xx that fit in the range 
      for (int x = 1; x <= M; x++) {
        int currOcc = occ[x][n];
        max = currOcc > max ? currOcc : max;

        ArrayList<Integer> xOccIndices = occIndices.get(x);
        for (int usedOcc = 1; usedOcc * 2 <= currOcc; usedOcc++) {
          int start = xOccIndices.get(usedOcc - 1);
          int end = xOccIndices.get(currOcc - usedOcc);
          for (int xx = 1; xx <= M; xx++) {
            if (xx != x) {
              ArrayList<Integer> xxOccIndices = occIndices.get(x);
              int maxWithPossibleXxOccs = 2 * usedOcc + occ[xx][end] - occ[xx][start];
              max = maxWithPossibleXxOccs > max ? maxWithPossibleXxOccs : max;
            }
          }
        }
      }

      output.append(max + "\n");
    }

    out.print(output);

    in.close();
    out.close();
  }

}