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

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

Вы можете выполнить следующую операцию над $$$s$$$ любое количество раз, чтобы достичь этого  —

       
  • Выберите любую подстроку $$$s$$$ и поверните ее по часовой стрелке один раз, то есть, если выбранная подстрока равна $$$s[l,l+1...r]$$$, то она становится равной $$$s[r,l,l + 1 ... r - 1]$$$. Все остальные символы $$$s$$$ остаются на своих местах.

    Например, при вращении подстроки $$$[2,4]$$$ строка «abcde» становится равной «adbce».

Строка $$$a$$$ является подстрокой $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) символов из начала и нескольких (возможно, ни одного или всех) символов из конца.

Найдите минимальное количество операций, необходимых для преобразования $$$s$$$ в $$$t$$$, или определите, что это невозможно.

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

Первая строка входных данных содержит одно целое число $$$t$$$ $$$(1\leq t \leq 2000)$$$ — количество наборов входных данных. Далее следуют описания наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ $$$(1\leq n \leq 2000)$$$ — длину строк.

Вторая и третья строки содержат строки $$$s$$$ и $$$t$$$ соответственно.

Сумма $$$n$$$ по всем наборам входных данных не превышает $$$2000$$$.

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

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

Пример
Входные данные
6
1
a
a
2
ab
ba
3
abc
cab
3
abc
cba
4
abab
baba
4
abcc
aabc
Выходные данные
0
1
1
2
1
-1
Примечание

Для первого набора входных данных, поскольку $$$s$$$ и $$$t$$$ равны, вам не нужно применять какие-либо операции.

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

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

Для четвертого набора входных данных вам нужно применить операцию дважды: сначала для всей строки abc, чтобы преобразовать ее в cab, а затем для подстроки длины $$$2$$$, начинающейся со второго символа для преобразования ее в cba.

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

Для шестого набора входных данных превратить строку $$$s$$$ в строку $$$t$$$ не является возможным.