A7249.字符串增生

有一天，Yuilice的好朋友Ruby给他出了一道字符串题目，Yuilice希望你可以帮他写一道程序，在1秒内快速计算出答案。

题目描述如下:

给出两个整数$N,M(1 \leq N,M \leq 25)$，同时输入长度为$N,M$的字符串$A,B$。

你可以对字符串$A$无限制次数的进行"增生"操作，"增生"操作效果为将当前的字符串$A$复制一份，黏贴连接在字符串$A$的末尾。

例: $A = Yuilice$,那么进行增生操作的效果如下。

字符串A	操作次数
Yuilice	0
YuiliceYuilice	1
YuiliceYuiliceYuiliceYuilice	2

Ruby希望知道，字符串$A$最少需要经过多少次增生，字符串B才能在字符串$A$中出现？输出最少次数。如果出现不了，那么输出-1。

输入第一行为一个正整数$t(1 \leq t \leq 10^4)$，代表接下来会有$t$组样例进行测试。

随后$t$组样例中，第一行输入两个整数$N,M$,代表字符串的长度。接下来两行分别输入字符串$A,B$。

输出一个整数代表最少增生次数。

第一组样例为增生1次

Yuilice -> YuiliceYuilice

第三组样例为增生1次，过程如下

babb -> babbbabb