CF2196E1 Fuzzy Concatenation (Easy Version)

这是该问题的简易版本。不同之处在于本题中 $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$，所需操作的最少次数。

每组测试数据包含多个测试用例。第一行包含整数 $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$。

每组测试用例输出一个整数，表示答案。

在第一个测试用例中，你可以从字符串 $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}» $$ 由 ChatGPT 5 翻译