CF2196E1.Fuzzy Concatenation (Easy Version)

This is the easy version of the problem. The difference between the versions is that in this version, $n \le 10^{5}, m \le 10^{4}$. You can hack only if you solved all versions of this problem.

There are two strings $s$ and $t$, both consisting of lowercase Latin letters. You also have an empty string $p$.

You can perform the following operation, which consists of several stages:

• choose any two integers $l$ and $r$ ($1 \le l \le r \le |s|$);
• copy the substring $s_{l},\ldots, s_{r}$ and append it to the end of string $p$;
• among the last $r - l + 1$ characters of string $p$, change at most one character to any lowercase Latin letter.

For example, if the string $s = $ "dhhtyhwbsl" and $p = $ "", you can choose $l = 3, r = 6$ and add "htyh" to the end of $p$, and then change the character "y" to "a", resulting in $p = $ "htah".

Your task is to determine the minimum number of operations required for string $p$ to become equal to $t$.

这是该问题的简单版本。两个版本的区别在于，在此版本中，$n \le 10^{5}, m \le 10^{4}$。仅当您已解决该问题的所有版本时，才可进行 hack。

给定两个字符串 $s$ 和 $t$，二者均由小写拉丁字母组成。此外，您还有一个空字符串 $p$。

您可以执行以下操作（该操作包含若干阶段）：

• 任选两个整数 $l$ 和 $r$（满足 $1 \le l \le r \le |s|$）；
• 复制子串 $s_{l},\ldots, s_{r}$，并将其追加到字符串 $p$ 的末尾；
• 在字符串 $p$ 的最后 $r - l + 1$ 个字符中，至多将其中一个字符修改为任意一个小写拉丁字母。

例如，若字符串 $s = $ "dhhtyhwbsl" 且 $p = $ ""，您可以选择 $l = 3, r = 6$，将 "htyh" 追加到 $p$ 末尾，然后将其中的字符 "y" 修改为 "a"，从而得到 $p = $ "htah"。

您的任务是确定使字符串 $p$ 变为与 $t$ 相等所需的最少操作次数。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n \le 10^{5}$, $1 \le m \le 10^{4}$) — the lengths of strings $s$ and $t$.

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

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

It is guaranteed that the sum of $n$ across all test cases does not exceed $10^{5}$, and the sum of $m$ across all test cases does not exceed $10^{4}$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 10^{5}$，$1 \le m \le 10^{4}$）—— 分别表示字符串 $s$ 和 $t$ 的长度。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，由小写拉丁字母组成。

每个测试用例的第三行包含一个长度为 $m$ 的字符串 $t$，由小写拉丁字母组成。

保证所有测试用例中 $n$ 的总和不超过 $10^{5}$，且所有测试用例中 $m$ 的总和不超过 $10^{4}$。

For each test case, output a single integer — the answer to the problem.

对于每个测试用例，输出一个整数——即该问题的答案。

In the first test case, you can take the substring $«\mathtt{a}»$ from the string $s$, change a single letter in this string to $«\mathtt{b}»$, and append it to the end of the string $p$, resulting in $p$ becoming equal to $t$.

In the second test case, $t$ can be obtained in $3$ operations as follows:

$$«\\mathtt{a\\color{red}{b}}» + «\\mathtt{\\color{red}{z}}» + «\\mathtt{\\color{red}{b}a}»$$

The modified characters are highlighted in red.

In the third test case, the string $t$ can be obtained as follows:

$$«\\mathtt{ht\\color{red}{a}h}» + «\\mathtt{bs\\color{red}{e}}» + «\\mathtt{htyh\\color{red}{z}b}»$$

在第一个测试用例中，你可以从字符串 $s$ 中取出子串 $«\mathtt{a}»$，将该子串中的一个字母修改为 $«\mathtt{b}»$，然后将其追加到字符串 $p$ 的末尾，从而使 $p$ 变为 $t$。

在第二个测试用例中，$t$ 可通过 $3$ 次操作得到，如下所示：

$$«\mathtt{a\color{red}{b}}» + «\mathtt{\color{red}{z}}» + «\mathtt{\color{red}{b}a}»$$

被修改的字符以红色高亮显示。

在第三个测试用例中，字符串 $t$ 可按如下方式得到：

$$«\mathtt{ht\color{red}{a}h}» + «\mathtt{bs\color{red}{e}}» + «\mathtt{htyh\color{red}{z}b}»$$