CF1701E.Text Editor

You wanted to write a text $t$ consisting of $m$ lowercase Latin letters. But instead, you have written a text $s$ consisting of $n$ lowercase Latin letters, and now you want to fix it by obtaining the text $t$ from the text $s$.

Initially, the cursor of your text editor is at the end of the text $s$ (after its last character). In one move, you can do one of the following actions:

• press the "left" button, so the cursor is moved to the left by one position (or does nothing if it is pointing at the beginning of the text, i. e. before its first character);
• press the "right" button, so the cursor is moved to the right by one position (or does nothing if it is pointing at the end of the text, i. e. after its last character);
• press the "home" button, so the cursor is moved to the beginning of the text (before the first character of the text);
• press the "end" button, so the cursor is moved to the end of the text (after the last character of the text);
• press the "backspace" button, so the character before the cursor is removed from the text (if there is no such character, nothing happens).

Your task is to calculate the minimum number of moves required to obtain the text $t$ from the text $s$ using the given set of actions, or determine it is impossible to obtain the text $t$ from the text $s$.

You have to answer $T$ independent test cases.

你想编写一个由 $m$ 个小写拉丁字母组成的文本 $t$。但实际却写出了一个由 $n$ 个小写拉丁字母组成的文本 $s$，现在你需要通过一系列操作将文本 $s$ 修改为文本 $t$。

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

• 按下“左”键，使光标向左移动一个位置（若光标已位于文本开头（即第一个字符之前），则无任何效果）；
• 按下“右”键，使光标向右移动一个位置（若光标已位于文本末尾（即最后一个字符之后），则无任何效果）；
• 按下“Home”键，使光标移动到文本开头（即第一个字符之前）；
• 按下“End”键，使光标移动到文本末尾（即最后一个字符之后）；
• 按下“退格”键（backspace），删除光标前的一个字符（若光标前无字符，则无任何效果）。

你的任务是：计算使用上述操作将文本 $s$ 变为文本 $t$ 所需的最少操作步数；若无法实现，则判定为不可能。

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

The first line of the input contains one integer $T$ ($1 \le T \le 5000$) — the number of test cases. Then $T$ test cases follow.

The first line of the test case contains two integers $n$ and $m$ ($1 \le m \le n \le 5000$) — the length of $s$ and the length of $t$, respectively.

The second line of the test case contains the string $s$ consisting of $n$ lowercase Latin letters.

The third line of the test case contains the string $t$ consisting of $m$ lowercase Latin letters.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5000$ ($\sum n \le 5000$).

输入的第一行包含一个整数 $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$）。

For each test case, print one integer — the minimum number of moves required to obtain the text $t$ from the text $s$ using the given set of actions, or -1 if it is impossible to obtain the text $t$ from the text $s$ in the given test case.

对于每个测试用例，输出一个整数——使用给定操作集从文本 $s$ 得到文本 $t$ 所需的最少移动次数；如果在该测试用例中无法从文本 $s$ 得到文本 $t$，则输出 -1。