E. Middle-Out
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вдохновением для задачи послужила история компании Pied Piper. После анонса технологии Nucleus со стороны конкурирующей компании Hooli Ричард при содействии друзей изобрёл принципиально новый подход к сжатию: «из середины наружу».

Вам даны две строки $$$s$$$ и $$$t$$$ одинаковой длины $$$n$$$. Пронумеруем их символы то $$$1$$$ до $$$n$$$ слева направо (т.е. от начала к концу)

За один ход вы можете сделать следующую последовательность действий:

  • выбрать произвольный индекс $$$i$$$ ($$$1 \le i \le n$$$),
  • передвинуть $$$i$$$-й символ строки $$$s$$$ с текущей позиции в начало строки или передвинуть $$$i$$$-й символ строки $$$s$$$ с текущей позиции в конец строки.

Заметим, что длина строки $$$s$$$ в результате хода не поменяется. Вы можете применить ход только к строке $$$s$$$.

Например, если $$$s=$$$«test», то за один ход можно получить:

  • если $$$i=1$$$ и вы перемещаете символ в начало, то результат будет равен «test» (строка не изменяется),
  • если $$$i=2$$$ и вы перемещаете символ в начало, то результат будет равен «etst»,
  • если $$$i=3$$$ и вы перемещаете символ в начало, то результат будет равен «stet»,
  • если $$$i=4$$$ и вы перемещаете символ в начало, то результат будет равен «ttes»,
  • если $$$i=1$$$ и вы перемещаете символ в конец, то результат будет равен «estt»,
  • если $$$i=2$$$ и вы перемещаете символ в конец, то результат будет равен «tste»,
  • если $$$i=3$$$ и вы перемещаете символ в конец, то результат будет равен «tets»,
  • если $$$i=4$$$ и вы перемещаете символ в конец, то результат будет равен «test» (строка не изменяется).

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

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

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

Описание каждого набора состоит из трёх строк. Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 100$$$) — длину строк $$$s$$$ и $$$t$$$. Вторая строка содержит строку $$$s$$$, третья строка содержит строку $$$t$$$. Строки $$$s$$$ и $$$t$$$ имеют длину $$$n$$$ и состоят только из строчных латинских букв.

Обратите внимание, что нет каких-либо ограничений на сумму значений $$$n$$$ во входных данных (т.е. тест с $$$q=100$$$ и всеми $$$n=100$$$ допустим).

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

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

Примеры
Входные данные
3
9
iredppipe
piedpiper
4
estt
test
4
tste
test
Выходные данные
2
1
2
Входные данные
4
1
a
z
5
adhas
dasha
5
aashd
dasha
5
aahsd
dasha
Выходные данные
-1
2
2
3
Примечание

В первом примере, ходы в одном из оптимальных ответов выглядят следующим образом:

  • в первом наборе: $$$s=$$$«iredppipe», $$$t=$$$«piedpiper»: «iredppipe» $$$\rightarrow$$$ «iedppiper» $$$\rightarrow$$$ «piedpiper»;
  • во втором наборе: $$$s=$$$«estt», $$$t=$$$«test»: «estt» $$$\rightarrow$$$ «test»;
  • в третьем наборе: $$$s=$$$«tste», $$$t=$$$«test»: «tste» $$$\rightarrow$$$ «etst» $$$\rightarrow$$$ «test».