CF1881A.Don't Try to Count

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.

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

每次操作中，你将当前的 $x$ 追加到 $x$ 的末尾。注意：执行该操作后，$x$ 的值会发生变化。

例如，若 $x =$ "aba"，则执行操作后，$x$ 的变化过程如下："aba" $\rightarrow$ "abaaba" $\rightarrow$ "abaabaabaaba"。

最少需要多少次操作，才能使 $s$ 作为子串出现在 $x$ 中？字符串的子串定义为该字符串中的一段连续字符序列。

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

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

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \cdot m \le 25$）—— 分别表示字符串 $x$ 和 $s$ 的长度。

每个测试用例的第二行包含长度为 $n$ 的字符串 $x$。

每个测试用例的第三行包含长度为 $m$ 的字符串 $s$。

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

对于每个测试用例，输出一个整数——使得字符串 $s$ 作为子串出现在字符串 $x$ 中所需的最少操作次数。如果无法实现，则输出 $-1$。

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.

在示例的第一个测试用例中，经过 $2$ 次操作后，字符串将变为 "aaaa"；经过 $3$ 次操作后，它将变为 "aaaaaaaa"，因此答案为 $3$。

在示例的第二个测试用例中，执行 $1$ 次操作后，字符串将变为 "$\text{e}\color{red}{\text{force}}\text{forc}$"，其中子串以红色高亮显示。

在示例的第四个测试用例中，可以证明无法使目标字符串作为子串出现。