给定一个长度为 $n$ 的字符串 $x$ 和一个长度为 $m$ 的字符串 $s$（满足 $n\cdot m\le 25$），两者均由小写拉丁字母组成。你可以对字符串 $x$ 执行任意次操作。

操作定义

一次操作中，将当前的 $x$ 追加到 $x$ 的末尾，即：

• 操作后 $x \leftarrow x + x$

注意：$x$ 的值会在每次操作后改变，因此下一次追加的是新的 $x$。

例如，若 $x=\text{"aba"}$，则变化为：

• "aba" → "abaaba" → "abaabaabaaba"

任务

求最少需要多少次操作后，字符串 $s$ 会作为 子串 出现在 $x$ 中。 子串 指字符串中的一个连续片段。

若无论进行多少次操作都不可能出现，则输出 $-1$。

输入格式

第一行输入一个整数 $t$（$1\le t\le 10^4$）表示测试用例数。

每个测试用例包含：

1. 一行两个整数 $n,m$（$1\le n\cdot m\le 25$）表示 $x$ 和 $s$ 的长度；
2. 一行长度为 $n$ 的字符串 $x$；
3. 一行长度为 $m$ 的字符串 $s$。

输出格式

对每个测试用例输出一行一个整数：

• 最少操作次数，使得 $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