F. Замена на подотрезке
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$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$$$.

Выходные данные

Для каждого теста выведите одно целое число — минимальное количество операций, которые вам нужно выполнить.

Пример
Входные данные
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