CF1572C.Paint

You are given a $1$ by $n$ pixel image. The $i$-th pixel of the image has color $a_i$. For each color, the number of pixels of that color is at most $20$.

You can perform the following operation, which works like the bucket tool in paint programs, on this image:

• pick a color — an integer from $1$ to $n$;
• choose a pixel in the image;
• for all pixels connected to the selected pixel, change their colors to the selected color (two pixels of the same color are considered connected if all the pixels between them have the same color as those two pixels).

Compute the minimum number of operations needed to make all the pixels in the image have the same color.

你有一张 $1$ 行 $n$ 列像素的图像。图像中第 $i$ 个像素的颜色为 $a_i$。每种颜色出现的像素数量至多为 $20$。

你可以对这张图像执行如下操作（类似于绘图软件中的“油漆桶”工具）：

• 选择一种颜色——一个从 $1$ 到 $n$ 的整数；
• 在图像中选择一个像素；
• 将所有与所选像素连通的像素的颜色均改为所选颜色（若两个同色像素之间的所有像素颜色均与这两个像素相同，则称这两个像素是连通的）。

请计算使图像中所有像素变为同一种颜色所需的最少操作次数。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^3$).

The first line of each test case contains a single integer $n$ ($1 \le n \le 3\cdot10^3$) — the number of pixels in the image.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — the colors of the pixels in the image.

Note: for each color, the number of pixels of that color is at most $20$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $3\cdot10^3$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, print one integer: the minimum number of operations needed to make all the pixels in the image have the same color.

对于每个测试用例，输出一个整数：使图像中所有像素变为同一种颜色所需的最少操作次数。

In the first example, the optimal solution is to apply the operation on the third pixel changing its color to $2$ and then to apply the operation on any pixel that has color $2$ changing its color and the color of all pixels connected to it to $1$. The sequence of operations is then: $[1, 2, 3, 2, 1] \to [1, 2, 2, 2, 1] \to [1, 1, 1, 1, 1]$.

In the second example, we can either change the $1$s to $2$s in one operation or change the $2$s to $1$s also in one operation.

In the third example, one possible way to make all the pixels have the same color is to apply the operation on the first, third and the fourth pixel each time changing its color to $2$.

在第一个例子中，最优解是：首先对第三个像素执行操作，将其颜色更改为 $2$；然后对任意一个颜色为 $2$ 的像素执行操作，将其颜色及所有与之连通的像素的颜色均更改为 $1$。操作序列为：$[1, 2, 3, 2, 1] \to [1, 2, 2, 2, 1] \to [1, 1, 1, 1, 1]$。

在第二个例子中，我们既可以通过一次操作将所有 $1$ 更改为 $2$，也可以通过一次操作将所有 $2$ 更改为 $1$。

在第三个例子中，一种使所有像素颜色相同的可行方法是：依次对第一个、第三个和第四个像素执行操作，每次均将其颜色更改为 $2$。