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

Даны строка $$$x$$$ длины $$$n$$$ и строка $$$s$$$ длины $$$m$$$ ($$$n \cdot m \le 25$$$), состоящие из строчных латинских букв. Вы можете применить любое количество операций к строке $$$x$$$.

За одну операцию вы приписываете текущее значение строки $$$x$$$ к концу $$$x$$$. Обратите внимание, что значение $$$x$$$ после этого изменится.

Например, если $$$x =$$$«aba», то при применении операций $$$x$$$ будет меняться следующим образом: «aba» $$$\rightarrow$$$ «abaaba» $$$\rightarrow$$$ «abaabaabaaba».

После какого минимального количества операций $$$s$$$ встретится в $$$x$$$ в качестве подстроки? Подстрокой строки называется любой её непрерывный отрезок.

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

В первой строке входных данных содержится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте.

Первая строка каждого набора содержит два числа $$$n$$$ и $$$m$$$ ($$$1 \le n \cdot m \le 25$$$) — длины строк $$$x$$$ и $$$s$$$ соответственно.

Вторая строка каждого набора содержит строку $$$x$$$ длины $$$n$$$.

Третья строка каждого набора содержит строку $$$s$$$ длины $$$m$$$.

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

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

Пример
Входные данные
12
1 5
a
aaaaa
5 5
eforc
force
2 5
ab
ababa
3 5
aba
ababa
4 3
babb
bbb
5 1
aaaaa
a
4 2
aabb
ba
2 8
bk
kbkbkbkb
12 2
fjdgmujlcont
tf
2 2
aa
aa
3 5
abb
babba
1 19
m
mmmmmmmmmmmmmmmmmmm
Выходные данные
3
1
2
-1
1
0
1
3
1
0
2
5
Примечание

В первом наборе входных данных примера, после $$$2$$$ применений операции строка станет равна «aaaa», а после $$$3$$$ «aaaaaaaa», так что ответ $$$3$$$.

Во втором наборе входных данных примера после применения $$$1$$$ операции строка станет равна «$$$\text{e}\color{red}{\text{force}}\text{forc}$$$», вхождение подстроки выделено красным.

В четвёртом наборе входных данных примера можно показать, что получить нужную строку как подстроку невозможно.