CF1922F Replace on Segment

给定一个数组 $a_1, a_2, \dots, a_n$，其中每个元素都是 $1$ 到 $x$ 之间的整数。 你可以对数组进行如下操作任意次： - 选择三个整数 $l$、$r$ 和 $k$，满足 $1 \le l \le r \le n$，$1 \le k \le x$，并且对于所有 $l \le i \le r$，都有 $a_i \ne k$。然后，将区间 $[l, r]$ 内的每个 $a_i$ 替换为 $k$。 换句话说，你可以选择数组的一个子区间和一个在该区间中未出现的整数 $k$（$1$ 到 $x$ 之间），然后将该区间内所有元素都替换为 $k$。 你的目标是让数组中所有元素都相等。请问最少需要多少次操作？

第一行包含一个整数 $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$。

对于每个测试用例，输出一个整数，表示最少需要多少次操作。

由 ChatGPT 4.1 翻译