给定一个数组 $$$a_1, a_2, \dots, a_n$$$,其中每个元素都是从 $$$1$$$ 到 $$$x$$$ 的整数。
您可以使用它执行以下操作任意次:
- 选择三个整数 $$$l$$$、$$$r$$$ 和 $$$k$$$,使得 $$$1 \le l \le r \le n$$$、$$$1 \le k \le x$$$ 以及每个元素 $$$a_i$$$ 使得 $$$l \le i \le r$$$ 与 $$$k$$$ 不同。然后,对于 [l, r]$$$ 中的每个 $$$i \in,将 $$$a_i$$$ 替换为 $$$k$$$。
换句话说,您选择数组的一个子段和一个从 $$$1$$$ 到 $$$x$$$ 之间未出现在该子段中的整数,并将子段中的每个元素替换为该所选整数。
您的目标是使数组中的所有元素相等。您必须执行的最少操作次数是多少?
输入
第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,打印一个整数 - 您必须执行的最少操作数。
示例
输入 #1
3 3 2 1 2 1 6 3 1 2 3 1 2 3 12 3 3 1 3 1 2 1 1 2 3 1 1 3
输出 #1
1 2 2