P16726 [GKS 2019 #B] Building Palindromes

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 能够回答“是”的问题个数。

在样例 #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 完成