希蒙的运动会项目匹配

题目描述

运动会共有26个项目，每个项目用唯一的小写字母标记（例如：a-田径，b-篮球，c-游泳，...z-攀岩）。希蒙负责管理两个项目序列 $a$ 和 $b$，每个序列包含 $n$ 个项目。

现在有 $q$ 次查询，每次给出区间 $[l, r]$。由于希蒙调皮地修改了 $a$ 序列中某些项目，你需要找到最少的修改次数，使得在区间 $[l, r]$ 内，$a$ 中每个项目的出现次数与 $b$ 中对应区间的项目出现次数完全相同。每次操作可以将 $a$ 中任意一个位置的项目修改为其他任意项目。

输入格式

第一行包含整数 $t$（$1 \leq t \leq 10$）——测试用例数。

每个测试用例：

1. 第一行两个整数 $n$ 和 $q$（$1 \leq n, q \leq 10^4$）
2. 第二行包含长度为 $n$ 的字符串 $a$，表示当前项目序列
3. 第三行包含长度为 $n$ 的字符串 $b$，表示目标项目序列
4. 接下来 $q$ 行，每行两个整数 $l$ 和 $r$（$1 \leq l \leq r \leq n$）

输出格式

对于每个查询，输出一个整数表示最少修改次数。

输入输出样例

输入 #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

样例解释

• 第一个测试用例的第2个查询：
  区间 [1-4] 的 $a$ 序列为 abcd，$b$ 序列为 edcb。需将 $a_1$ 从田径(a)改为击剑(e)，使各项目数量匹配。

• 第二个测试用例的第1个查询：
  区间 [1-3] 的 $a$ 序列为 zzd（3个足球），$b$ 序列为 azb（1田径+1篮球+1足球），需修改2个位置。

希蒙想知道：至少需要多少次修改，才能让被选中的区间恢复正确的项目分布？