CFCF2196E2.Fuzzy Concatenation (Hard version)

这是这个问题的难度较高的版本。不同之处在于本版本中 $n \le 5 \cdot 10^{5}, m \le 5 \cdot 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 5 \cdot 10^{5}, 1 \le m \le 5 \cdot 10^{4}$）——字符串 $s$ 和 $t$ 的长度。

接下来一行给出长度为 $n$ 的字符串 $s$，仅包含小写字母。

再下一行给出长度为 $m$ 的字符串 $t$，也只包含小写字母。

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

对于每个测试用例，输出一个整数，表示最少操作次数。

在第一个测试用例中，你可以从字符串 $s$ 中取出子串 "a"，将其中唯一的字母修改成 "b"，并将其添加到 $p$ 的末尾，这样 $p$ 就等于 $t$ 了。

在第二个测试用例中，可以通过 $3$ 次操作生成 $t$：

$$\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}$$