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

Обратите внимание, что единственная разница между Трансформация строки 1 и Трансформация строки 2 заключается в операции, которую делает Коа. В этой версии буква $$$y$$$, которую выбирает Koa, может быть любой из первых $$$20$$$ букв английского алфавита (для лучшего понимания прочитайте условие). Вы можете делать взломы по этим задачам независимо.

Коала Коа имеет две строки $$$A$$$ и $$$B$$$ одинаковой длины $$$n$$$ ($$$|A|=|B|=n$$$), состоящие из первых $$$20$$$ строчных букв английского алфавита (то есть от a до t).

В один ход Коа:

  1. выбирает некоторое подмножество позиций $$$p_1, p_2, \ldots, p_k$$$ ($$$k \ge 1; 1 \le p_i \le n; p_i \neq p_j$$$ если $$$i \neq j$$$) из $$$A$$$, такое что $$$A_{p_1} = A_{p_2} = \ldots = A_{p_k} = x$$$ (т. е. все буквы на этой позиции равны некоторой букве $$$x$$$).

  2. выбирает любую букву $$$y$$$ (из первых $$$20$$$ строчных букв английского алфавита).

  3. делает все буквы в позициях $$$p_1, p_2, \ldots, p_k$$$ равными $$$y$$$. Более формально: для каждого $$$i$$$ ($$$1 \le i \le k$$$) Коа устанавливает $$$A_{p_i} = y$$$.

    Обратите внимание, что вы можете изменять только буквы в строке $$$A$$$.

Коа хочет знать наименьшее число ходов, которые она должна сделать, чтобы сделать строки равными друг другу ($$$A = B$$$) или определить, что нет никакого способа сделать их равными. Помогите ей!

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

Каждый тест содержит несколько наборов входных данных. Первая строка содержит $$$t$$$ ($$$1 \le t \le 10$$$) — количество наборов входных данных. Описание наборов входных данных приведено ниже.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — длину строк $$$A$$$ и $$$B$$$.

Вторая строка каждого набора входных данных содержит строку $$$A$$$ ($$$|A|=n$$$).

Третья строка каждого набора входных данных содержит строку $$$B$$$ ($$$|B|=n$$$).

Обе строки состоят из первых строчных букв английского алфавита $$$20$$$ (т.е. от a до t).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$10^5$$$.

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

Для каждого набора входных данных:

Выведите в единственной строке минимальное количество ходов, которое Koa должна сделать, чтобы строки стали равны друг другу ($$$A = B$$$) или $$$-1$$$, если нет никакого способа сделать их равными.

Пример
Входные данные
5
3
aab
bcc
4
cabc
abcb
3
abc
tsr
4
aabd
cccd
5
abcbd
bcdda
Выходные данные
2
3
3
2
4
Примечание
  • В $$$1$$$-м наборе входных данных Koa:
    1. выбирает позиции $$$1$$$ и $$$2$$$ и устанавливает $$$A_1 = A_2 = $$$ b ($$$\color{red}{aa}b \rightarrow \color{blue}{bb}b$$$).
    2. выбирает позиции $$$2$$$ и $$$3$$$ и устанавливает $$$A_2 = A_3 = $$$ c ($$$b\color{red}{bb} \rightarrow b\color{blue}{cc}$$$).

  • В $$$2$$$-м наборе входных данных Koa:
    1. выбирает позиции $$$1$$$ и $$$4$$$ и устанавливает $$$A_1 = A_4 = $$$ a ($$$\color{red}{c}ab\color{red}{c} \rightarrow \color{blue}{a}ab\color{blue}{a}$$$).
    2. выбирает позиции $$$2$$$ и $$$4$$$ и устанавливает $$$A_2 = A_4 = $$$ b ($$$a\color{red}{a}b\color{red}{a} \rightarrow a\color{blue}{b}b\color{blue}{b}$$$).
    3. выбирает позицию $$$3$$$ и устанавливает $$$A_3 = $$$ c ($$$ab\color{red}{b}b \rightarrow ab\color{blue}{c}b$$$).

  • В $$$3$$$-м наборе входных данных Koa:
    1. выбирает позицию $$$1$$$ и устанавливает $$$A_1 = $$$ t ($$$\color{red}{a}bc \rightarrow \color{blue}{t}bc$$$).
    2. выбирает позицию $$$2$$$ и устанавливает $$$A_2 = $$$ s ($$$t\color{red}{b}c \rightarrow t\color{blue}{s}c$$$).
    3. выбирает позицию $$$3$$$ и устанавливает $$$A_3 = $$$ r ($$$ts\color{red}{c} \rightarrow ts\color{blue}{r}$$$).