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
from collections import defaultdict, deque
from itertools import permutations, product, combinations
from functools import lru_cache
from time import time
import sys
from operator import itemgetter

start = time()


def show_time():
    print(time() - start, file=sys.stderr)


try:
    f = open('test.in')


    def ints():
        return map(int, f.readline().strip().split())


    def one_int():
        return int(f.readline())


    def one_string():
        return f.readline().strip()


    def strings():
        return f.readline().strip().split()
except FileNotFoundError:
    def ints():
        return map(int, input().strip().split())


    def one_int():
        return int(input())


    def one_string():
        return input().strip()


    def strings():
        return input().strip().split()


def debug(s):
    print(s, file=sys.stderr)


sys.stderr.write('\n')
"""
    problem specific code starts here
"""
from collections import Counter
def ans(numbers, rev_numbers, a, c):
    r = max(c.values())
    for i in range(0, 1 + c[a] // 2):
        ia, rev_ia = set_indices(a, i, numbers, rev_numbers)
        if (ia, rev_ia) == (-1, -1):
            continue
        if rev_ia == 0:
            sub_list = numbers[ia:]
        else:
            sub_list = numbers[ia:(-rev_ia)]
        if sub_list:
            sub_counter = Counter(sub_list)
            r = max(r, 2 * i + max(sub_counter.values()))
        else:
            r = max(r, 2 * i)
    return r

@lru_cache(maxsize=None)
def set_indices(a, i, numbers, rev_numbers):
    if i == 0:
        return 0, 0

    ia, rev_ia = set_indices(a, i - 1, numbers, rev_numbers)

    try:
        ia += numbers[ia:].index(a)
        ia += 1
        rev_ia += rev_numbers[rev_ia:].index(a)
        rev_ia += 1
    except ValueError:
        ia, rev_ia = -1, -1
    if ia + rev_ia > len(numbers):
        ia, rev_ia = -1, -1
    return ia, rev_ia


t = one_int()
for _ in range(t):
    n = one_int()
    numbers = tuple(list(ints()))
    rev_numbers = numbers[::-1]
    c = Counter(numbers)
    r = max(c.values())
    for a in set(numbers):
        r = max(r, ans(numbers, rev_numbers, a, c))
    print(r)
