题目描述

有 $N$ 个小球排成一排，每个小球都有一种颜色。第 $i$ 个小球的颜色用正整数 $c_i$ 表示，颜色编号满足 $1 \le c_i \le C$。

在游戏过程中，你可以在当前序列的任意位置插入若干个小球，插入的小球颜色也必须在 $1$ 到 $C$ 之间。你也可以反复执行如下消除操作：选择当前序列中连续的三个小球，如果第一个小球和第三个小球颜色相同，就可以将这三个小球同时删除。删除后，左右两侧剩余小球会重新相邻。插入操作和消除操作可以按任意顺序交替进行。

例如，对于颜色序列 $1\ 2\ 1\ 3$，可以选择前三个小球 $1\ 2\ 1$ 并将它们删除，剩余序列为 $3$。

请你计算，至少需要插入多少个小球，才能使整个序列最终被全部消除。

输入格式

第一行包含一个整数 $T$，表示测试用例组数。

对于每组测试用例：

• 第一行包含两个整数 $N, C$，分别表示初始小球数量和颜色种类数。
• 第二行包含 $N$ 个整数 $c_1, c_2, \dots, c_N$，表示初始序列中每个小球的颜色。

输出格式

对于每组测试用例，输出一行，一个整数，表示最少需要插入的小球数量。

3
4 2
1 2 1 2
5 3
1 2 3 2 1
3 3
1 2 3

2
1
3

提示

【样例说明】

第一组数据中，可以插入两个颜色为 $2$ 的小球，使序列变为 $2\ 1\ 2\ 2\ 1\ 2$。先删除前三个小球 $2\ 1\ 2$，再删除剩余的 $2\ 1\ 2$，即可全部消除。因此答案为 $2$。

第二组数据中，可以先删除中间的 $2\ 3\ 2$，剩下 $1\ 1$。再插入一个颜色为 $2$ 的小球，得到 $1\ 2\ 1$ 并将其删除。因此答案为 $1$。

第三组数据中，至少需要插入 $3$ 个小球。例如，先插入两个颜色为 $1$ 的小球形成 $1\ 1\ 1$ 并删除，剩余 $2\ 3$；再插入一个颜色为 $2$ 的小球形成 $2\ 3\ 2$ 并删除。

【评测用例规模与约定】

对于 $30\%$ 的评测用例，$N \le 15$。

对于所有评测用例，$T \le 20$，$1 \le N \le 300$，$1 \le C \le 10$，$1 \le c_i \le C$。