题目描述

你本来想写一个由 $m$ 个小写拉丁字母组成的文本 $t$，但实际上你写成了一个由 $n$ 个小写拉丁字母组成的文本 $s$，现在你想通过编辑操作将 $s$ 变成 $t$。

一开始，文本编辑器的光标位于文本 $s$ 的末尾（即最后一个字符之后）。每次操作，你可以进行以下操作之一：

• 按下“左”键，将光标向左移动一个位置（如果光标已经在文本开头，即第一个字符之前，则无效）；
• 按下“右”键，将光标向右移动一个位置（如果光标已经在文本末尾，即最后一个字符之后，则无效）；
• 按下“Home”键，将光标移动到文本开头（即第一个字符之前）；
• 按下“End”键，将光标移动到文本末尾（即最后一个字符之后）；
• 按下“Backspace”键，删除光标前的一个字符（如果前面没有字符，则无效）。

你的任务是计算，使用上述操作，将文本 $s$ 变为文本 $t$ 所需的最少操作次数，或者判断在本测试用例下是否无法将 $s$ 变为 $t$。

你需要回答 $T$ 个独立的测试用例。

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。接下来是 $T$ 个测试用例。

每个测试用例的第一行包含两个整数 $n$ 和 $m$，分别表示 $s$ 和 $t$ 的长度。

第二行为长度为 $n$ 的字符串 $s$，由小写拉丁字母组成。

第三行为长度为 $m$ 的字符串 $t$，由小写拉丁字母组成。

输出格式

对于每个测试用例，输出一个整数，表示将 $s$ 变为 $t$ 所需的最少操作次数。如果无法将 $s$ 变为 $t$，则输出 $-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

5
6
3
4
4
-1

说明 / 提示

由 ChatGPT 4.1 翻译

1
1 1
a
a

0

1
5 1
abcde
a

4

数据范围

保证所有测试用例中 $n$ 的总和不超过 $5000$（$\sum n \le 5000$）。

（$1 \le T \le 5000$）

（$1 \le m \le n \le 5000$）