C. Сортировка
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны две строки $$$a$$$ и $$$b$$$ длиной $$$n$$$. Затем вам (против вашей воли) придется ответить на $$$q$$$ запросов.

Для каждого запроса вам дан отрезок, ограниченный позициями $$$l$$$ и $$$r$$$. За одну операцию вы можете выбрать целое число $$$i$$$ ($$$l \leq i \leq r$$$) и установить $$$a_i = x$$$, где $$$x$$$ — любой символ, который вы захотите. Выведите минимальное количество операций, которые вам нужно выполнить, чтобы $$$\texttt{sorted(a[l..r])} = \texttt{sorted(b[l..r])}$$$. Операции, которые вы выполняете в одном запросе, не влияют на другие запросы.

Для произвольной строки $$$c$$$, $$$\texttt{sorted(c[l..r])}$$$ обозначает подстроку, состоящую из символов $$$c_l, c_{l+1}, ... , c_r$$$, отсортированных в лексикографическом порядке.

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

Первая строка содержит $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных.

Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \leq n, q \leq 2 \cdot 10^5$$$) — длина обеих строк и количество запросов.

Следующая строка содержит строку $$$a$$$ длины $$$n$$$. Гарантируется, что $$$a$$$ содержит только строчные латинские буквы.

Следующая строка содержит строку $$$b$$$ длины $$$n$$$. Гарантируется, что $$$b$$$ содержит только строчные латинские буквы.

Следующие $$$q$$$ строк содержат два целых числа $$$l$$$ и $$$r$$$ ($$$1 \leq l \leq r \leq n$$$) — отрезок запроса.

Гарантируется, что сумма $$$n$$$ и $$$q$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

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

Для каждого запроса выведите целое число, минимальное количество операций, которые вам нужно выполнить, на новой строке.

Пример
Входные данные
3
5 3
abcde
edcba
1 5
1 4
3 3
4 2
zzde
azbe
1 3
1 4
6 3
uwuwuw
wuwuwu
2 4
1 3
1 6
Выходные данные
0
1
0
2
2
1
1
0
Примечание

Для первого запроса $$$\texttt{sorted(a[1..5])} =$$$ abcde и $$$\texttt{sorted(b[1..5])} =$$$ abcde, поэтому операции не требуются.

Для второго запроса вам нужно установить $$$a_1 = $$$ e. Тогда $$$\texttt{sorted(a[1..4])} = \texttt{sorted(b[1..4])} = $$$ bcde.