← 返回题目列表

Codeforces · 1881/A

A. 不要尝试数数

中文机器翻译题面 查看原题

给定一个长度为 $$$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}$$$”,其中子字符串以红色突出显示。

在示例的第四个测试用例中,可以看出不可能获得所需的字符串作为子字符串。