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). 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}). For each test case, output a single integer — the answer to the problem. In the first test case, you can take the substring («\mathtt{a}») from the string (s), change a