题目描述

斌宝在玩纸牌。起初，他有 $n$ 张牌，第 $i$ 张牌的点数为 $A_i$。

斌宝会重复执行 $n$ 轮以下操作，第 $i$ 轮操作如下：

1. 斌宝需要选择将第 $i$ 张牌置于插入牌堆的最左边或者最右边；
2. 若牌堆中存在两张点数相同的牌，则斌宝会立即将两张牌之间的所有牌从牌堆取出，扔进碎纸机（包括这两张牌本身）。

总是会先执行插入操作再执行粉碎操作。

牌堆初始为空。

你需要告诉斌宝他最多能粉碎多少张牌。

输入格式

第一行，一个整数 $T$，表示数据组数。

对于每组数据：

第一行一个整数 $n$。

第二行 $n$ 个数表示 $A_1,A_2,A_3,\cdots,A_n$。

输出格式

对于每组数据，输出斌宝最多能粉碎多少张牌。

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

提示

样例解释

初始牌堆：$\{\}$

放入 $1$：$\{1\}$；

放入 $3$：$\{1,3\}$；

放入 $3$：$\{3,1,3\}$，然后粉碎：$\{\}$；

放入 $1$：$\{1\}$；

放入 $2$：$\{1,2\}$；

放入 $1$：$\{1,2,1\}$，然后粉碎：$\{\}$；

放入 $2$：$\{2\}$；

放入 $2$：$\{2,2\}$，然后粉碎：$\{\}$；

所有牌均被粉碎。

数据范围

子任务	分值	限制
$0$	$20$	$n\le 20$
$1$		$T=1,n=10^3$ 且 $A_i$ 在 $[1,n]$ 内随机生成
$2$	$40$	$n\le10^3$
$3$	$20$	-

对于 $100\%$ 的数据，$1\le T\le5$，$1\le n\le5\times10^5$，$1\le A_i\le n$。