E2. Нечеткая склейка (сложная версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии $$$n \le 5 \cdot 10^{5}, m \le 5 \cdot 10^{4}$$$. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Даны две строки $$$s$$$ и $$$t$$$, обе строки состоят из строчных латинских букв. Также у вас есть пустая строка $$$p$$$.

Вы можете совершать следующую операцию, состоящую из нескольких этапов:

  • выбрать любые два целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le |s|$$$);
  • скопировать подстроку $$$s_{l},\ldots, s_{r}$$$ и добавить её в конец строки $$$p$$$;
  • среди последних $$$r - l + 1$$$ символов строки $$$p$$$ изменить не более одного символа на любую строчную латинскую букву.

Например, если строка $$$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$$$.

Вторая строка каждого набора входных данных содержит строку $$$s$$$ длины $$$n$$$, состоящую из строчных букв латинского алфавита.

Третья строка каждого набора входных данных содержит строку $$$t$$$ длины $$$m$$$, состоящую из строчных букв латинского алфавита.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$5 \cdot 10^{5}$$$, а также сумма $$$m$$$ по всем наборам входных данных не превосходит $$$5 \cdot 10^{4}$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — ответ на задачу.

Пример
Входные данные
4
1 1
a
b
5 5
aaaaa
abzba
10 13
dhhtyhwbsl
htahbsehtyhzb
7 2
contest
on
Выходные данные
1
3
3
1
Примечание

В первом наборе входных данных можно взять подстроку $$$«\mathtt{a}»$$$ строки $$$s$$$, изменить единственную букву в этой строке на $$$«\mathtt{b}»$$$ и добавить в конец строки $$$p$$$, в результате $$$p$$$ станет равна $$$t$$$.

Во втором наборе $$$t$$$ можно получить за $$$3$$$ операции следующим образом:

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