C. Покраска
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть изображение размером $$$1$$$ на $$$n$$$ пикселей. $$$i$$$-й пиксель изображения имеет цвет $$$a_i$$$. Для каждого цвета число пикселей, имеющих этот цвет, не более $$$20$$$.

Вы можете выполнять следующую операцию, которая обычно называется «заливка» в редакторах изображений:

  • выбрать цвет — целое число от $$$1$$$ до $$$n$$$;
  • выбрать некоторый пиксель изображения;
  • изменить цвет всех связных с выбранным пикселем на выбранный цвет (два пикселя одного цвета называются связными, если все пиксели между ними имеют такой же цвет, как и эти два пикселя).

Вычислите минимальное количество операций, необходимое, чтобы все пиксели изображения стали одного цвета.

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

Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^3$$$) — количество наборов входных данных. Далее следуют наборы входных данных.

Первая строка набора входных данных содержит $$$n$$$ ($$$1 \le n \le 3\cdot10^3$$$) — количество пикселей.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — начальные цвета пикселей в изображении.

Обратите внимание, что для каждого цвета число пикселей, имеющих этот цвет, не более $$$20$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$3\cdot10^3$$$.

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

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

Пример
Входные данные
3
5
1 2 3 2 1
4
1 1 2 2
5
1 2 1 4 2
Выходные данные
2
1
3
Примечание

В первом примере оптимальное решение — применить операцию на третьем пикселе, изменив его цвет на $$$2$$$, и затем применить операцию на любом пикселе цвета $$$2$$$, изменив его и всех связных пикселей цвет на $$$1$$$. Последовательность операций тогда будет: $$$[1, 2, 3, 2, 1] \to [1, 2, 2, 2, 1] \to [1, 1, 1, 1, 1]$$$.

Во втором примере мы можем либо изменить все $$$1$$$ на $$$2$$$ за одну операцию, или все $$$2$$$ на $$$1$$$ также за одну операцию.

В третьем примере один из возможных способов сделать все пиксели одного цвета — применить операцию на первом, третьем и четвертом пикселе, каждый раз выбирая цвет $$$2$$$.