E. Лексикографически достаточно малая
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны две строки $$$s$$$ и $$$t$$$ равной длины $$$n$$$. За одну операцию вы можете поменять местами любые два соседних символа в строке $$$s$$$.

Вам нужно сказать, какое наименьшее количество операций вам потребуется, чтобы строка $$$s$$$ стала лексикографически меньше строки $$$t$$$.

Строка $$$a$$$ лексикографически меньше строки $$$b$$$, если и только если выполняется один из следующих пунктов:

  • $$$a$$$ — префикс $$$b$$$, но $$$a \ne b$$$;
  • в первой позиции, где $$$a$$$ и $$$b$$$ различны, в строке $$$a$$$ находится буква, которая встречается в алфавите раньше, чем соответствующая буква в $$$b$$$.
Входные данные

Первая строка входных данных содержит одно целое число $$$q$$$ ($$$1 \le q \le 10\,000$$$): количество тестовых случаев.

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

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

Третья строка каждого тестового случая содержит строку $$$t$$$ из $$$n$$$ строчных букв латинского алфавита.

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

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

Для каждого тестового случая в отдельной строке выведите наименьшее количество операций, которое вам потребуется, чтобы строка $$$s$$$ стала лексикографически меньше строки $$$t$$$, или $$$-1$$$, если это невозможно сделать.

Пример
Входные данные
4
1
a
a
3
rll
rrr
3
caa
aca
5
ababa
aabba
Выходные данные
-1
0
2
2