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