No submission language available for this problem.

Background

Special for beginners, ^_^

Description

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

题目描述如下:

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

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

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

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

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

Format

Input

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

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

Output

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

Samples

5
7 4
Yuilice
eYui
1 4
c
cccc
4 3
babb
bbb
7 7
Yuilice
Yuilice
2 5
bc
bcbcb

1
2
1
0
2

Limitation

提示说明 第一组样例为增生1次

Yuilice -> YuiliceYuilice

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

babb -> babbbabb

1s, 1024KiB for each test case.