Triple Palindrome Sequence

Problem Description

You are given a sequence $a$ of length $n$.

We define a triple palindrome sequence as a sequence of the form $\underbrace{a\dots a}_{k_1}\ \underbrace{b\dots b}_{k_2}\ \underbrace{a\dots a}_{k_1}$. For example: $[1,1,1,2,2,1,1,1]$ is a triple palindrome sequence, while $[1,1,1,2,2,2,3,3,3]$ and $[1,1,2,2,1]$ are not.

Now, find the length of the longest triple palindrome subsequence in the sequence $a$.

Note that $k_1, k_2$ may be $0$.

Input Format

The first line gives an integer $T$, the number of test cases.

For each test case:

The first line gives the length $n$ of the sequence.

The second line gives $a_1, a_2, a_3, \dots, a_n$.

Output Format

For each test case, output the length of the longest triple palindrome subsequence.

Sample 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

Sample Output

7
2
4
1
1
3

Constraints

$1\le t\le 2000$

$1\le \sum n\le 2\cdot 10^5,\ 1\le a_i \le 26$