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
T = int(input())

Q = []

# Read all inputs before computing (see last comment, the goal is to print once)
for t in range(T):
    N = int(input())
    A = [int(_) for _ in input().split()]
    Q.append((N, A))

R = []
for N, A in Q:
    # Switch the 2 dimensions of the array to maybe prevent cache miss on loops l27
    prefC = [[0] * (26) for _ in range(N+1)]
    for c in range(26):
        for i in range(N):
            prefC[i+1][c] = prefC[i][c]
            if A[i] == c+1:
                prefC[i+1][c] += 1

    answer = 0
    for l in range(N):
        for r in range(l, N):
            cntin = 0
            cntout = 0
            # Write the explicit loop, don't use max on the list comprehension (x2 constant factor inside the N² loop)
            for c in range(26):
                cntin = max(cntin, prefC[r+1][c] - prefC[l][c])
                cntout = max(cntout, min(prefC[l][c], prefC[N][c] - prefC[r+1][c]))
            answer = max(answer, 2 * cntout + cntin)
    R.append(answer)

# Do only one print instead of T prints (less stdout flushing I guess)
print('\n'.join(map(str, R)))
