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.

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

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

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.