您想要编写由 $$$m$$$ 小写拉丁字母组成的文本 $$$t$$$。相反,您编写了由 $$$n$$$ 小写拉丁字母组成的文本 $$$s$$$,现在您想通过从文本 $$$s$$$ 获取文本 $$$t$$$ 来修复它。
最初,文本编辑器的光标位于文本 $$$s$$$ 的末尾(在其最后一个字符之后)。您可以一步执行以下操作之一:
- 按“向左”按钮,使光标向左移动一个位置(或者如果光标指向文本的开头,即第一个字符之前,则不执行任何操作);
- 按“向右”按钮,使光标向右移动一个位置(或者如果光标指向文本末尾,即在最后一个字符之后,则不执行任何操作);
- 按“home”按钮,使光标移动到文本的开头(文本的第一个字符之前);
- 按“结束”按钮,使光标移动到文本末尾(文本最后一个字符之后);
- 按“退格”按钮,因此光标之前的字符将从文本中删除(如果没有该字符,则不会发生任何情况)。
你的任务是计算使用给定的一组动作从文本$$$s$$$获取文本$$$t$$$所需的最小移动次数,或者确定不可能从文本$$$s$$$获取文本$$$t$$$。
您必须回答 $$$T$$$ 独立测试用例。
输入
输入的第一行包含一个整数 $$$T$$$ ($$$1 \le T \le 5000$$$) — 测试用例的数量。然后是 $$$T$$$ 测试用例。
测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le m \le n \le 5000$$$) — 分别是 $$$s$$$ 的长度和 $$$t$$$ 的长度。
测试用例的第二行包含由 $$$n$$$ 小写拉丁字母组成的字符串 $$$s$$$。
测试用例的第三行包含由 $$$m$$$ 小写拉丁字母组成的字符串 $$$t$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5000$$$ ($$$\sum n \le 5000$$$)。
输出
对于每个测试用例,打印一个整数 — 使用给定的一组操作从文本 $$$s$$$ 获取文本 $$$t$$$ 所需的最小移动次数,如果在给定测试用例中无法从文本 $$$s$$$ 获取文本 $$$t$$$,则打印 -1。
示例
输入 #1
6 9 4 aaaaaaaaa aaaa 7 3 abacaba aaa 5 4 aabcd abcd 4 2 abba bb 6 4 baraka baka 8 7 question problem
输出 #1
5 6 3 4 4 -1