题目描述

在图书馆中，有一个长度为 $n$ 的书架，上面依次摆放着 $n$ 本书，编号为 $a_1, a_2, \ldots, a_n$。每本书的编号代表其所属的类别。

图书管理员可以进行如下操作：选择一个位置 $i$（$1 \le i < n$），如果 $a_i \ne a_{i+1}$，则可以将这两本不同类别的相邻书籍同时从书架上移除。移除后，书架上的书籍会自动向左对齐，填补空缺。

管理员希望通过若干次（可能为零次）上述操作，使得书架上剩下的书籍编号全部相同。请你计算，在最优操作策略下，书架上剩下的书籍数量最多为多少。

输入格式

输入包含多组测试数据。第一行是一个整数 $T$，表示测试数据的组数。接下来的 $T$ 组数据，每组数据包括两行：

• 第一行是一个整数 $n$，表示书架上书籍的数量。
• 第二行是 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示书籍的编号。

输出格式

对于每组测试数据，输出一个整数，表示在最优操作策略下，书架上剩下的书籍编号全部相同的最大数量。

输入输出样例 #1

输入 #1

5
9
5 3 3 5 2 5 5 2 1
9
3 5 4 4 1 3 5 4 3
6
1 2 3 5 5 4
2
5 5
2
3 1

输出 #1

3
3
0
2
0

数据范围与提示

• $1 \le T \le 1000$
• $1 \le n \le 5000$
• $1 \le a_i \le n$

保证所有测试数据中，$n$ 的总和不超过 $10000$。