Problem Description

Binbao is playing cards. At first, he has $n$ cards, and the value of the $i$-th card is $A_i$.

Binbao will repeatedly perform the following operation for $n$ rounds. The operation in round $i$ is:

1. Binbao needs to choose to place the $i$-th card on the leftmost side or the rightmost side of the pile.
2. If there exist two cards in the pile with the same value, then Binbao will immediately take all cards between these two cards out of the pile and throw them into the shredder (including these two cards themselves).

The insertion operation is always performed before the shattering operation.

The pile is initially empty.

You need to tell Binbao the maximum number of cards he can shatter.

Input Format

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

For each test case:

The first line contains an integer $n$.

The second line contains $n$ numbers representing $A_1,A_2,A_3,\cdots,A_n$.

Output Format

For each test case, output the maximum number of cards Binbao can shatter.

4
8
1 3 3 1 2 1 2 2
8
3 2 2 1 2 1 2 1
6
1 2 1 2 1 2
6
1 2 3 4 5 6

8
7
6
0

Hint

Sample Explanation

Initial pile: $\{\}$

Put in $1$: $\{1\}$;

Put in $3$: $\{1,3\}$;

Put in $3$: $\{3,1,3\}$, then shatter: $\{\}$;

Put in $1$: $\{1\}$;

Put in $2$: $\{1,2\}$;

Put in $1$: $\{1,2,1\}$, then shatter: $\{\}$;

Put in $2$: $\{2\}$;

Put in $2$: $\{2,2\}$, then shatter: $\{\}$;

All cards are shattered.

Constraints

For $100\%$ of the testdata, $1\le T\le5$, $1\le n\le5\times10^5$, $1\le A_i\le n$.

Translated by ChatGPT 5