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.