Paint

Description:

Input:

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$$$.

Output:

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.

Sample Input:

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

Sample Output:

2
1
3

Note:

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$$$.