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

У вас есть строка $$$a$$$ и строка $$$b$$$. Обе строки имеют длину $$$n$$$. В строке $$$a$$$ содержится не более $$$10$$$ различных символов. У вас также есть множество $$$Q$$$. Изначально множество $$$Q$$$ пусто. Вы можете применить следующую операцию к строке $$$a$$$ любое количество раз:

  • Выберите индекс $$$i$$$ ($$$1\leq i \leq n$$$) и строчный латинскую букву $$$c$$$. Добавьте $$$a_i$$$ в множество $$$Q$$$ и замените $$$a_i$$$ на $$$c$$$.

Например, пусть строка $$$a$$$ — это «$$$\tt{abecca}$$$». Мы можем выполнить следующие операции:

  • В первой операции, если выбрать $$$i = 3$$$ и $$$c = \tt{x}$$$, символ $$$a_3 = \tt{e}$$$ будет добавлен к множеству $$$Q$$$. Таким образом, множество $$$Q$$$ будет равняться $$$\{\tt{e}\}$$$, а строка $$$a$$$ станет «$$$\tt{ab\underline{x}cca}$$$».
  • Во второй операции, если выбрать $$$i = 6$$$ и $$$c = \tt{s}$$$, то символ $$$a_6 = \tt{a}$$$ будет добавлен к множеству $$$Q$$$. Таким образом, множество $$$Q$$$ будет равняться $$$\{\tt{e}, \tt{a}\}$$$, а строка $$$a$$$ будет «$$$\tt{abxcc\underline{s}}$$$».

Со строкой $$$a$$$ можно выполнить любое количество операций, но в конце множество $$$Q$$$ должно содержать не более $$$k$$$ различных символов. Учитывая это ограничение, вам нужно максимизировать количество пар целых чисел $$$(l, r)$$$ ($$$1\leq l\leq r \leq n$$$) таких, что $$$a[l,r] = b[l,r]$$$. Здесь $$$s[l,r]$$$ означает подстроку строки $$$s$$$, начинающуюся с индекса $$$l$$$ (включительно) и заканчивающуюся индексом $$$r$$$ (включительно).

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1\leq n \leq 10^5$$$, $$$0\leq k\leq 10$$$) — длина двух строк и ограничение на размер множества $$$Q$$$.

Вторая строка содержит строку $$$a$$$ длины $$$n$$$. В строке $$$a$$$ содержится не более $$$10$$$ различных символов.

Последняя строка содержит строку $$$b$$$ длины $$$n$$$.

Обе строки $$$a$$$ и $$$b$$$ содержат только строчные латинские буквы. Сумма $$$n$$$ по всем наборам входных данных не превышает $$$10^5$$$.

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

Для каждого набора входных данных выведите в строке одно целое число — максимальное количество пар $$$(l, r)$$$, удовлетворяющих ограничениям.

Пример
Входные данные
6
3 1
abc
abd
3 0
abc
abd
3 1
xbb
xcd
4 1
abcd
axcb
3 10
abc
abd
10 3
lkwhbahuqa
qoiujoncjb
Выходные данные
6
3
6
6
6
11
Примечание

В первом наборе входных данных мы можем выбрать индекс $$$i = 3$$$ и заменить его символом $$$c = \tt{d}$$$. Все возможные пары $$$(l,r)$$$ будут удовлетворять условию.

Во втором наборе мы не можем выполнить ни одну операцию. $$$3$$$ удовлетворяющие условию пары $$$(l,r)$$$:

  1. $$$a[1,1] = b[1,1] =$$$ «$$$\tt{a}$$$»,
  2. $$$a[1,2] = b[1,2] =$$$ «$$$\tt{ab}$$$»,
  3. $$$a[2,2] = b[2,2] =$$$ «$$$\tt{b}$$$».

В третьем наборе мы можем выбрать индекс $$$2$$$ и индекс $$$3$$$ и заменить их символами $$$\tt{c}$$$ и $$$\tt{d}$$$ соответственно. Множество $$$Q$$$ в конце будет равняться $$$\{\tt{b}\}$$$ (размер равен $$$1$$$, не превышает $$$k$$$). Все возможные пары $$$(l,r)$$$ будут подходить под условие.