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, \dots, a}_{x}, \underbrace{b, b, \dots, b}_{y}, \underbrace{a, a, \dots, 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 \le t \le 2000$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains one integer $n$ ($1 \le n \le 2000$) — the length of $a$. The second line of the test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 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$ ($\sum n \le 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

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'for _ in range(int(input())):\n\tn = int(input())\n\tr = list(map(int, input().split()))\n\td = {i: [] for i in range(1, 27)}\n\tfor i in range(n):\n\t\td[r[i]].append(i)\n\tans = 1\n\tfor end in range(1, 27):\n\t\tc = 1\n\t\twhile c * 2 <= len(d[end]):\n\t\t\tll, rr = d[end][c - 1] + 1, d[end][-c] - 1\n\t\t\tdd = [0] * 27\n\t\t\tfor p in range(ll, rr + 1):\n\t\t\t\tdd[r[p]] += 1\n\t\t\tans = max(ans, max(dd) + 2 * c)\n\t\t\tc += 1\n\tprint (ans)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13465