区间替换

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

给定一个长度为 $n$ 的数组 $a_1,a_2,\ldots,a_n$，每个元素都是 $1$ 到 $x$ 之间的整数。

一次操作中，你可以选择三个整数 $l,r,k$，满足 $1\le l\le r\le n$、$1\le k\le x$，并且区间 $[l,r]$ 中没有任何元素等于 $k$。随后，将该区间内的所有元素都替换为 $k$。

你的目标是让整个数组中的元素全部相等。请计算所需的最少操作次数。

输入格式

第一行包含一个整数 $t$，表示测试用例数量。

每个测试用例包含两行：

第一行包含两个整数 $n,x$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

对于每个测试用例，输出一个整数，表示让数组所有元素相等所需的最少操作次数。

样例输入 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

数据范围

对于所有数据，$1\le t\le100$，$1\le x\le n\le100$，$1\le a_i\le x$，所有测试用例的 $n$ 之和不超过 $500$。