D. Раскраска палиндромов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть строка $$$s$$$, состоящая из строчных букв латинского алфавита.

Вы можете покрасить некоторые буквы в цвета от $$$1$$$ до $$$k$$$. Необязательно красить все буквы. Для каждого цвета должна быть буква, покрашенная в этот цвет.

Затем вы можете сколько угодно раз менять местами любые два символа, покрашенные в один цвет.

После этого будет создано $$$k$$$ строк, $$$i$$$-я из них будет содержать все символы, покрашенные в цвет $$$i$$$, записанные в порядке их следования в строке $$$s$$$.

Ваша задача покрасить символы строки так, чтобы все полученные $$$k$$$ строк были палиндромами, а длина самой короткой из этих $$$k$$$ строк была как можно больше.

Прочтите пояснение к первому набору входных данных примера, если вам требуется пояснение к условию задачи.

Напомним, что строка является палиндромом, если она читается одинаково как слева направо, так и справа налево. Например, строки abacaba, cccc, z и dxd являются палиндромами, а строки abab и aaabaa — нет.

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

Первая строка входных данных содержит единственное целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте.

Далее следуют описания наборов входных данных.

Первая строка описания каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$) — длина строки и число цветов, в которые можно красить её буквы. Вторая строка описания каждого набора входных данных содержит строку $$$s$$$ длины $$$n$$$, состоящую из строчных букв латинского алфавита.

Гарантируется, что сумма длин всех строк в тесте не превосходит $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
10
8 2
bxyaxzay
6 3
aaaaaa
6 1
abcdef
6 6
abcdef
3 2
dxd
11 2
abcabcabcac
6 6
sipkic
7 2
eatoohd
3 1
llw
6 2
bfvfbv
Выходные данные
3
2
1
1
1
5
1
1
3
3
Примечание
  • В первом наборе входных данных $$$s$$$=«bxyaxzay», $$$k=2$$$. Далее будем использовать индексы в строке от $$$1$$$ до $$$8$$$. Подойдет следующая раскраска: $$$\mathtt{\mathbf{\color{red}{b}\color{blue}{xy}\color{red}{a}\color{blue}{x}z\color{red}{a}\color{blue}{y}}}$$$ (буква z осталась непокрашенной). После покраски:
    • поменяем местами два красных символа (с индексами $$$1$$$ и $$$4$$$) местами, получим $$$\mathtt{\mathbf{\color{red}{a}\color{blue}{xy}\color{red}{b}\color{blue}{x}z\color{red}{a}\color{blue}{y}}}$$$;
    • поменяем местами два синих символа (с индексами $$$5$$$ и $$$8$$$) местами, получим $$$\mathtt{\mathbf{\color{red}{a}\color{blue}{xy}\color{red}{b}\color{blue}{y}z\color{red}{a}\color{blue}{x}}}$$$.

    Теперь, если для каждого из двух цветов выписать соответствующие буквы слева направо, то получим две строки $$$\mathtt{\mathbf{\color{red}{aba}}}$$$ и $$$\mathtt{\mathbf{\color{blue}{xyyx}}}$$$. Обе они являются палиндромами, длина наименьшей равна $$$3$$$. Можно показать, что большую длину наименее длинного палиндрома достичь нельзя.

  • Во втором наборе входных данных подойдёт такая раскраска: $$$[1, 1, 2, 2, 3, 3]$$$. Менять символы местами не нужно. Обе полученные строки равны aa, они являются палиндромами и их длина равна $$$2$$$.
  • В третьем наборе входных данных можно покрасить любой символ и взять его в строку.
  • В четвёртом наборе входных данных можно покрасить $$$i$$$-й символ в цвет $$$i$$$.
  • В пятом наборе входных данных можно покрасить в каждый из цветов по одному символу.
  • В шестом наборе входных данных подойдёт такая раскраска: $$$[1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 0]$$$. Переставим символы так, чтобы получить палиндромы abcba и acbca.