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$.

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.

Samples

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