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

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

Изначально курсор вашего текстового редактора находится в конце текста $$$s$$$ (после последнего символа текста). За один ход вы можете совершить одно из следующих действий:

  • нажать кнопку «влево», таким образом, курсор переместится на одну позицию влево (или не сделает ничего, если он уже указывает на начало текста, то есть стоит перед первым символом текста);
  • нажать кнопку «вправо», таким образом, курсор переместится на одну позицию вправо (или не сделает ничего, если он уже указывает на конец текста, то есть стоит после последнего символа текста);
  • нажать кнопку «home», таким образом, курсор переместится в начало текста (на позицию перед первым символом текста);
  • нажать кнопку «end», таким образом, курсор переместится в конец текста (на позицию после последнего символа текста);
  • нажать кнопку «backspace», таким образом, символ слева от курсора удалится из текста (если такого символа нет, ничего не произойдет).

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

Вам необходимо ответить на $$$T$$$ независимых наборов тестовых данных.

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

Первая строка входных данных содержит одно целое число $$$T$$$ ($$$1 \le T \le 5000$$$) — количество наборов тестовых данных. Затем следуют $$$T$$$ наборов тестовых данных.

Первая строка набора содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le m \le n \le 5000$$$) — длину $$$s$$$ и длину $$$t$$$, соответственно.

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

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

Гарантируется, что сумма $$$n$$$ по всем наборам тестовых данных не превосходит $$$5000$$$ ($$$\sum n \le 5000$$$).

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

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

Пример
Входные данные
6
9 4
aaaaaaaaa
aaaa
7 3
abacaba
aaa
5 4
aabcd
abcd
4 2
abba
bb
6 4
baraka
baka
8 7
question
problem
Выходные данные
5
6
3
4
4
-1