Вы хотели написать текст \(t\), состоящий из \(m\) строчных букв латинского алфавита. Но вместо этого вы написали текст \(s\), состоящий из \(n\) строчных букв латинского алфавита, и теперь вы хотите исправить это, получив текст \(t\) из текста \(s\).
Изначально курсор вашего текстового редактора находится в конце текста \(s\) (после последнего символа текста). За один ход вы можете совершить одно из следующих действий:
- нажать кнопку «влево», таким образом, курсор переместится на одну позицию влево (или не сделает ничего, если он уже указывает на начало текста, то есть стоит перед первым символом текста);
- нажать кнопку «вправо», таким образом, курсор переместится на одну позицию вправо (или не сделает ничего, если он уже указывает на конец текста, то есть стоит после последнего символа текста);
- нажать кнопку «home», таким образом, курсор переместится в начало текста (на позицию перед первым символом текста);
- нажать кнопку «end», таким образом, курсор переместится в конец текста (на позицию после последнего символа текста);
- нажать кнопку «backspace», таким образом, символ слева от курсора удалится из текста (если такого символа нет, ничего не произойдет).
Ваша задача — посчитать минимальное количество ходов, необходимое для того, чтобы получить текст \(t\) из текста \(s\) при помощи заданного набора действий, или же определить, что невозможно получить текст \(t\) из текста \(s\).
Вам необходимо ответить на \(T\) независимых наборов тестовых данных.
Выходные данные
Для каждого набора выведите одно целое число — минимальное количество ходов, необходимое для того, чтобы получить текст \(t\) из текста \(s\) при помощи заданного набора действий, или же -1, если невозможно получить текст \(t\) из текста \(s\) в данном наборе тестовых данных.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|