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