F. 区间替换

时间限制：每个测试 $3$ 秒
内存限制：每个测试 $256$ MB

给定一个数组 $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, r]$ 内的每个元素 $a_i$ 都不等于 $k$。然后，将子段 $[l, r]$ 内的每个元素替换为 $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$。

输出

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

样例

输入

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
2
2