E2. Fuzzy Concatenation (Hard version)
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Example
Input
4
1 1
a
b
5 5
aaaaa
abzba
10 13
dhhtyhwbsl
htahbsehtyhzb
7 2
contest
on
Output
1
3
3
1
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}»$$$$$$