310748: CF1881A. Don't Try to Count

A. Don't Try to Counttime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Given a string $x$ of length $n$ and a string $s$ of length $m$ ($n \cdot m \le 25$), consisting of lowercase Latin letters, you can apply any number of operations to the string $x$.

In one operation, you append the current value of $x$ to the end of the string $x$. Note that the value of $x$ will change after this.

For example, if $x =$"aba", then after applying operations, $x$ will change as follows: "aba" $\rightarrow$ "abaaba" $\rightarrow$ "abaabaabaaba".

After what minimum number of operations $s$ will appear in $x$ as a substring? A substring of a string is defined as a contiguous segment of it.

Input

The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains two numbers $n$ and $m$ ($1 \le n \cdot m \le 25$) — the lengths of strings $x$ and $s$, respectively.

The second line of each test case contains the string $x$ of length $n$.

The third line of each test case contains the string $s$ of length $m$.

Output

For each test case, output a single number — the minimum number of operations after which $s$ will appear in $x$ as a substring. If this is not possible, output $-1$.

ExampleInput

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

Output

3
1
2
-1
1
0
1
3
1
0
2
5

Note

In the first test case of the example, after $2$ operations, the string will become "aaaa", and after $3$ operations, it will become "aaaaaaaa", so the answer is $3$.

In the second test case of the example, after applying $1$ operation, the string will become "$\text{e}\color{red}{\text{force}}\text{forc}$", where the substring is highlighted in red.

In the fourth test case of the example, it can be shown that it is impossible to obtain the desired string as a substring.

题目大意：
给定一个长度为n的字符串x和一个长度为m的字符串s（n*m≤25），它们由小写拉丁字母组成。你可以对字符串x执行任意次数的操作。每次操作时，你将当前字符串x的值附加到x的末尾。注意，操作后x的值会改变。求出最少需要多少次操作，使得s成为x的一个子串。如果不可能，输出-1。

输入数据格式：
第一行输入一个整数t（1≤t≤10^4），表示测试用例的数量。
每个测试用例包含三行：
第一行是两个整数n和m（1≤n*m≤25），分别表示字符串x和s的长度。
第二行是长度为n的字符串x。
第三行是长度为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
```题目大意： 给定一个长度为n的字符串x和一个长度为m的字符串s（n*m≤25），它们由小写拉丁字母组成。你可以对字符串x执行任意次数的操作。每次操作时，你将当前字符串x的值附加到x的末尾。注意，操作后x的值会改变。求出最少需要多少次操作，使得s成为x的一个子串。如果不可能，输出-1。 输入数据格式： 第一行输入一个整数t（1≤t≤10^4），表示测试用例的数量。 每个测试用例包含三行： 第一行是两个整数n和m（1≤n*m≤25），分别表示字符串x和s的长度。 第二行是长度为n的字符串x。 第三行是长度为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 ```