311024: CF1922F. Replace on Segment

F. Replace on Segmenttime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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?

Input

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$.

Output

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

ExampleInput

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

Output

1
2
2

题目大意：
给定一个数组 $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$ 不同。然后，对于每个 $i \in [l, r]$，将 $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。

输出数据格式：
对于每个测试用例，打印一个整数——需要执行的最少操作次数。题目大意： 给定一个数组 $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$ 不同。然后，对于每个 $i \in [l, r]$，将 $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。 输出数据格式： 对于每个测试用例，打印一个整数——需要执行的最少操作次数。