给定两个字符串 $$$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$$$) – 两个字符串的长度和查询的数量。
以下行包含长度为 $$$n$$$ 的 $$$a$$$。保证 $$$a$$$ 仅包含小写拉丁字母。
以下行包含长度为 $$$n$$$ 的 $$$b$$$。保证 $$$b$$$ 仅包含小写拉丁字母。
以下 $$$q$$$ 行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \leq l \leq r \leq n$$$) – 查询的范围。
保证所有测试用例的 $$$n$$$ 和 $$$q$$$ 之和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个查询,输出一个整数,即需要在新行中执行的最少操作数。
示例
输入 #1
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
输出 #1
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。