CF1922F.Replace on Segment

You are given an array $a_1, a_2, \dots, a_n$, where each element is an integer from $1$ to $x$.

You can perform the following operation with it any number of times:

• choose three integers $l$, $r$ and $k$ such that $1 \le l \le r \le n$, $1 \le k \le x$ and each element $a_i$ such that $l \le i \le r$ is different from $k$. Then, for each $i \in [l, r]$, replace $a_i$ with $k$.

In other words, you choose a subsegment of the array and an integer from $1$ to $x$ which does not appear in that subsegment, and replace every element in the subsegment with that chosen integer.

Your goal is to make all elements in the array equal. What is the minimum number of operations that you have to perform?

给你一个数组 $a_1, a_2, \dots, a_n$，其中每个元素均为 $1$ 到 $x$ 之间的整数。

你可以对该数组执行以下操作任意多次：

• 选择三个整数 $l$、$r$ 和 $k$，满足 $1 \le l \le r \le n$、$1 \le k \le x$，且对每个下标 $i$ 满足 $l \le i \le r$，均有 $a_i \ne k$。然后，对每个 $i \in [l, r]$，将 $a_i$ 替换为 $k$。

换言之，你选择数组的一个子区间以及一个 $1$ 到 $x$ 之间的整数 $k$，要求该整数在所选子区间中未出现，再将该子区间内的所有元素全部替换为 $k$。

你的目标是使数组中所有元素相等。你至少需要执行多少次操作？

The first line contains one integer $t$ ($1 \le t \le 100$) — the number of test cases.

Each test case consists of two lines:

• the first line contains two integers $n$ and $x$ ($1 \le x \le n \le 100$);
• the second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le x$).

Additional constraint on the input: the sum of $n$ over all test cases does not exceed $500$.

第一行包含一个整数 $t$（$1 \le t \le 100$）—— 表示测试用例的数量。

每个测试用例由两行组成：

• 第一行包含两个整数 $n$ 和 $x$（$1 \le x \le n \le 100$）；
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le x$）。

输入的附加约束：所有测试用例的 $n$ 值之和不超过 $500$。

For each test case, print one integer — the minimum number of operations you have to perform.

对于每个测试用例，输出一个整数——你需要执行的最少操作次数。