This is the hard version of the problem. The difference between the versions is that in this version, $$$n \le 5 \cdot 10^{5}, m \le 5 \cdot 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$$$.

Input

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 5 \cdot 10^{5}, 1 \le m \le 5 \cdot 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 $$$5 \cdot 10^{5}$$$, and the sum of $$$m$$$ across all test cases does not exceed $$$5 \cdot 10^{4}$$$.

Output

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

Note

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

Fuzzy Concatenation (Hard version)

Examples