您将获得一张由 $$$n$$$ 像素组成的 $$$1$$$ 图像。图像的第 $$$i$$$ 个像素的颜色为 $$$a_i$$$。对于每种颜色,该颜色的像素数最多为$$$20$$$。
您可以在此图像上执行以下操作,其作用类似于绘画程序中的水桶工具:
- 选择一种颜色 - 从 $$$1$$$ 到 $$$n$$$ 的整数;
- 选择图像中的一个像素;
- 对于连接到所选像素的所有像素,将其颜色更改为所选颜色(如果两个像素之间的所有像素都与这两个像素具有相同的颜色,则将相同颜色的两个像素视为连接)。
计算使图像中的所有像素具有相同颜色所需的最少操作数。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3\cdot10^3$$$) — 图像中的像素数。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — 图像中像素的颜色。
注意:对于每种颜色,该颜色的像素数最多为$$$20$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$3\cdot10^3$$$。
输出
对于每个测试用例,打印一个整数:使图像中所有像素具有相同颜色所需的最少操作数。
示例
输入 #1
3 5 1 2 3 2 1 4 1 1 2 2 5 1 2 1 4 2
输出 #1
2 1 3
注意
在第一个示例中,最佳解决方案是将操作应用于将其颜色更改为 $$$2$$$ 的第三个像素,然后将操作应用于将颜色 $$$2$$$ 更改为颜色的任何像素以及与其连接的所有像素的颜色为 $$$1$$$。则操作顺序为:$$$[1, 2, 3, 2, 1] \to [1, 2, 2, 2, 1] \to [1, 1, 1, 1, 1]$$$。
在第二个示例中,我们可以在一次操作中将 $$$1$$$s 更改为 $$$2$$$s,也可以在一次操作中将 $$$2$$$s 更改为 $$$1$$$s。
在第三个示例中,使所有像素具有相同颜色的一种可能方法是每次将其颜色更改为 $$$2$$$ 时对第一、第三和第四个像素应用操作。