题目描述

Anna 有一排 $N$ 个积木，每个积木上恰好写有一个从 A 到 Z 的字母。积木从左到右编号为 $1, 2, \dots, N$。

今天，她在学习回文。回文是指正着读和反着读都相同的字符串。例如，ANNA、RACECAR、AAA 和 X 都是回文，而 AB、FROG 和 YOYO 则不是。

Bob 想测试 Anna 对回文的理解程度，他会问她 $Q$ 个问题。第 $i$ 个问题是：Anna 能否使用编号从 $L_i$ 到 $R_i$（包含两端）的所有积木，在必要时重新排列它们，形成一个回文？在每个问题之后，Anna 会将积木放回原来的位置。

请帮助 Anna 找出她能够回答“是”的问题有多少个。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $N$ 和 $Q$，分别表示积木的数量和问题的数量。随后一行包含一个由 $N$ 个大写字母（A 到 Z）组成的字符串。接着有 $Q$ 行，第 $i$ 行包含两个整数 $L_i$ 和 $R_i$，描述第 $i$ 个问题。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是 Anna 能够回答“是”的问题个数。

2
7 5
ABAACCA
3 6
4 4
2 5
6 7
3 7
3 5
XYZ
1 3
1 3
1 3
1 3
1 3

Case #1: 3
Case #2: 0

提示

在样例 #1 中，$N = 7$，$Q = 5$。

• 对于第一个问题，Anna 必须使用积木 AACC。她可以将这些积木重新排列成回文 ACCA（或 CAAC）。
• 对于第二个问题，Anna 必须使用积木 A。这本身已经是回文，因此她不需要重新排列。
• 对于第三个问题，Anna 必须使用积木 BAAC。这些积木无法重新排列成回文。
• 对于第四个问题，Anna 必须使用积木 CA。这些积木无法重新排列成回文。
• 对于第五个问题，Anna 必须使用积木 AACCA。她可以将这些积木重新排列成回文 ACACA（或 CAAAC）。

总共，她能够对 Bob 的 $3$ 个问题回答“是”，因此答案为 $3$。

在样例 #2 中，$N = 3$，$Q = 5$。对于第一个问题，Anna 必须使用积木 XYZ 来构造回文，这是不可能的，并且其余问题与第一个相同，因此答案为 $0$。

限制条件

$1 \le T \le 100$。

$1 \le L_i \le R_i \le N$。

测试集 1（可见）

$1 \le N \le 20$。

$1 \le Q \le 20$。

测试集 2（隐藏）

$1 \le N \le 10^5$。

$1 \le Q \le 10^5$。

翻译由 DeepSeek V4 Pro 完成