给定一个长度为 $$$n$$$ 的字符串 $$$x$$$ 和一个长度为 $$$m$$$ ($$$n \cdot m \le 25$$$) 且由小写拉丁字母组成的字符串 $$$s$$$,您可以对字符串 $$$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$$$ 的长度。
每个测试用例的第二行包含长度为 $$$n$$$ 的字符串 $$$x$$$。
每个测试用例的第三行包含长度为$$$m$$$的字符串$$$s$$$。
输出
对于每个测试用例,输出一个数字 - 最少的操作次数,之后 $$$s$$$ 将作为子字符串出现在 $$$x$$$ 中。如果不可能,则输出 $$$-1$$$。
示例
输入 #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
输出 #1
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}$$$”,其中子字符串以红色突出显示。
在示例的第四个测试用例中,可以看出不可能获得所需的字符串作为子字符串。