CF 1996C - Sort

给定两个长度为 n 的字符串 a 和 b。然后，你（被迫）回答 q 个查询。

对于每个查询，给定一个由 l 和 r 界定的范围。在一次操作中，你可以选择一个整数 i (l≤i≤r) 并设置 ai=x，其中 x 是你想要的任何字符。输出你必须执行的最少操作数，使得 sorted(a[l..r])=sorted(b[l..r])。你对一个查询执行的操作不会影响其他查询。

对于任意字符串 c，sorted(c[l..r]) 表示由字符 cl、cl+1、...、cr 按字典顺序排序的子字符串。

输入

第一行包含 t (1≤t≤1000) – 测试用例的数量。

每个测试用例的第一行包含两个整数 n 和 q (1≤n,q≤2⋅105) – 两个字符串的长度和查询的数量。

以下行包含长度为 n 的 a。保证 a 仅包含小写拉丁字母。

以下行包含长度为 n 的 b。保证 b 仅包含小写拉丁字母。

以下 q 行包含两个整数 l 和 r (1≤l≤r≤n) – 查询的范围。

保证所有测试用例的 n 和 q 的总和不超过 2⋅105。

输出

对于每个查询，在新行中输出一个整数，即您需要执行的最少操作数。