Description

一个外星机器人正在威胁宇宙，它使用一束光束，能够摧毁所有的算法知识。我们必须阻止它！

幸运的是，我们已经了解了机器人的工作方式。它一开始拥有强度为 $1$ 的光束，并将运行一个由一系列指令组成的程序，这些指令会按从左到右的顺序依次执行。每条指令有以下两种类型之一：

• c（代表“充能”）：将光束的强度加倍。
• s（代表“发射”）：发射光束，造成等于当前光束强度的伤害。

例如，如果机器人的程序是 sccssc，当程序运行时，机器人会按如下方式执行：

• 发射光束，造成 $1$ 点伤害。
• 充能，将光束强度加倍至 $2$。
• 充能，将光束强度加倍至 $4$。
• 发射光束，造成 $4$ 点伤害。
• 发射光束，造成 $4$ 点伤害。
• 充能，将光束强度加倍至 $8$。

在这种情况下，程序总共会造成 $9$ 点伤害。

宇宙顶尖的算法专家们开发了一种护盾，最多可以承受 $\mathbf D$ 点总伤害。但机器人的当前程序在运行时可能会造成超过这个数值的伤害。

宇宙总统自愿飞入太空，在机器人运行程序之前对其进行黑客攻击。总统唯一能在不被机器人察觉的情况下进行的黑客手段，是交换两条相邻的指令。例如，总统可以通过交换上述程序的第三和第四条指令，将其变为 scscsc，这样总伤害就会降为 $7$。然后，总统还可以再次进行黑客操作，将程序变为 scsscc，总伤害降为 $5$，以此类推。

为了避免引起机器人的怀疑，总统不希望进行太多次黑客操作。请问，最少需要多少次黑客操作，才能确保程序造成的总伤害不超过 $\mathbf D$，如果无法做到，则输出 IMPOSSIBLE。

Input Format

输入的第一行包含测试用例的数量 $\mathbf{T}$。接下来有 $\mathbf{T}$ 组测试用例。每组测试用例包含一行，包括一个整数 $\mathbf{D}$ 和一个字符串 $\mathbf{P}$，分别表示护盾能承受的最大总伤害，以及机器人的程序。

Output Format

对于每组测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是完成目标所需的最小黑客次数，或者如果无法实现则输出 IMPOSSIBLE。

6
1 CS
2 CS
1 SS
6 SCCSSC
2 CC
3 CSCSS

Case #1: 1
Case #2: 0
Case #3: IMPOSSIBLE
Case #4: 2
Case #5: 0
Case #6: 5

Hint

样例解释

注意，最后三个样例不会出现在测试集 1 中。

在样例 1 中，总统可以交换两条指令，将总伤害降为 $1$，护盾可以承受。

在样例 2 中，总统无需进行任何黑客操作，因为程序造成的总伤害为 $2$，护盾可以承受。

在样例 3 中，程序造成的伤害超过了护盾的承受能力，并且无论如何黑客都无法改变这一点。宇宙注定要毁灭。

样例 4 使用了题目描述中的程序。题目中演示了一种通过两次黑客操作将总伤害降为 $5$ 的方法。仅用一次黑客操作无法将伤害降至 $6$ 或以下；请记住，总统只能交换相邻的指令。

在样例 5 中，机器人永远不会发射，因此不会造成任何伤害，无需黑客操作。

在样例 6 中，需要进行五次黑客操作。注意，即使两次黑客操作交换的是同一对位置的指令，也算作两次操作。

数据范围

• $1 \leq T \leq 100$。
• $1 \leq D \leq 10^9$。
• $2 \leq P$ 的长度 $\leq 30$。
• $P$ 中的每个字符都是 $c$ 或 $s$。

测试集 1（5 分，可见）

机器人的程序中最多只包含 $0$ 个或 $1$ 个 $c$ 字符。

测试集 2（10 分，隐藏）

无额外限制。

由 ChatGPT 4.1 翻译