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.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Objects;
import java.util.Random;
import java.util.StringTokenizer;

public class E {

  static MyScanner scanner = new MyScanner();
  static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
  static final int MOD = 1000000007;
  static final boolean oj = System.getProperty("ONLINE_JUDGE") != null;

  public static void main(String[] args) {
    int tc = scanner.nextInt();
    for(int t=0; t<tc; t++) {
      int n = scanner.nextInt();
      int[][] m = new int[n+1][];
      m[0] = new int[200];
      int res = 0;
      for(int i=0; i<n; i++) {
        int cv = scanner.nextInt()-1;
        m[i+1] = m[i].clone();
        m[i+1][cv]++;
        res = Math.max(res, m[i+1][cv]);
      }
      for(int st=0; st<200; st++) {
        int l = 1, r = n, k = 1;
        while(l < r) {
          while(l<r && m[l][st] < k) l++;
          while(l<r && m[n][st]-m[r][st] < k) r--;
          if(l >= r) break;
          for(int j=0; j<200; j++) {
            if(st == j) continue;
            res = Math.max(res, 2*k+m[r][j] - m[l][j]);
          }
          k++;
        }
      }
      out.println(res);
    }
    out.close();
  }

  public static void print(Object o) {
    if(!oj) {
      out.println(o);
    }
  }

  //Find the GCD of two numbers
  public static long gcd(long a, long b) {
    if (a < b) return gcd(b,a);
    if (b == 0)
      return a;
    else
      return gcd(b,a%b);
  }

  //Fast exponentiation (x^y mod m)
  public static long power(long x, long y, long m) {
    if (y < 0) return 0L;
    long ans = 1;
    x %= m;
    while (y > 0) {
      if(y % 2 == 1)
        ans = (ans * x) % m;
      y /= 2;
      x = (x * x) % m;
    }
    return ans;
  }

  public static int[] shuffle(int[] array) {
    Random rgen = new Random();
    for (int i = 0; i < array.length; i++) {
      int randomPosition = rgen.nextInt(array.length);
      int temp = array[i];
      array[i] = array[randomPosition];
      array[randomPosition] = temp;
    }
    return array;
  }

  public static long[] shuffle(long[] array) {
    Random rgen = new Random();
    for (int i = 0; i < array.length; i++) {
      int randomPosition = rgen.nextInt(array.length);
      long temp = array[i];
      array[i] = array[randomPosition];
      array[randomPosition] = temp;
    }
    return array;
  }

  public static int[][] shuffle(int[][] array) {
    Random rgen = new Random();
    for (int i = 0; i < array.length; i++) {
      int randomPosition = rgen.nextInt(array.length);
      int[] temp = array[i];
      array[i] = array[randomPosition];
      array[randomPosition] = temp;
    }
    return array;
  }

  public static int[][] sort(int[][] array) {
    //Sort an array (immune to quicksort TLE)

    Arrays.sort(array, new Comparator<int[]>() {
      @Override
      public int compare(int[] a, int[] b) {
        return a[1]-b[1]; //ascending order
      }
    });
    return array;
  }

  public static long[][] sort(long[][] array) {
    //Sort an array (immune to quicksort TLE)
    Random rgen = new Random();
    for (int i = 0; i < array.length; i++) {
      int randomPosition = rgen.nextInt(array.length);
      long[] temp = array[i];
      array[i] = array[randomPosition];
      array[randomPosition] = temp;
    }
    Arrays.sort(array, new Comparator<long[]>() {
      @Override
      public int compare(long[] a, long[] b) {
        if (a[0] < b[0])
          return -1;
        else if (a[0] > b[0])
          return 1;
        else
          return 0;
      }
    });
    return array;
  }

  static class MyScanner {
    private BufferedReader br;
    private StringTokenizer st;

    MyScanner() {
      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 class Pair<K,V> {

    public K key;
    public V value;

    public Pair(K key, V value) {
      this.key = key;
      this.value = value;
    }

    @Override
    public String toString() {
      return key + ":" + value;
    }

    @Override
    public int hashCode() {
      return key.hashCode() * 13 + (value == null ? 0 : value.hashCode());
    }

    @Override
    public boolean equals(Object o) {
      if (this == o) return true;
      if (o instanceof Pair) {
        Pair pair = (Pair) o;
        return Objects.equals(key, pair.key) && Objects.equals(value, pair.value);
      }
      return false;
    }
  }

  static class Triple<A, B, C> {
    public A a;
    public B b;
    public C c;

    public Triple(A a, B b, C c) {
      this.a = a;
      this.b = b;
      this.c = c;
    }

    @Override
    public String toString() {
      return a + ":" + b + ":" + c;
    }

    @Override
    public int hashCode() {
      return (a == null ? 0 : a.hashCode()) * 13 + (b == null ? 0 : b.hashCode()) * 41 + (c == null ? 0 : c.hashCode());
    }

    @Override
    public boolean equals(Object o) {
      if (this == o) return true;
      if (o instanceof Triple) {
        Triple triple = (Triple) o;
        return Objects.equals(a, triple.a) && Objects.equals(b, triple.b) && Objects.equals(c, triple.c);
      }
      return false;
    }
  }
}
