Saving the universe again

An alien robot is threatening the universe with a beam that destroys all algorithmic knowledge. We have to stop it.

Fortunately, we know how the robot works. It starts with a beam of strength 1 and runs a program, which is a series of instructions executed one at a time from left to right. Each instruction is one of two types:

• C (charge): doubles the beam's strength.
• S (shoot): fires the beam, dealing damage equal to the beam's current strength.

For example, if the program is SCCSSC, the robot does the following:

• Shoots the beam, dealing 1 damage.
• Charges the beam, doubling its strength to 2.
• Charges the beam, doubling its strength to 4.
• Shoots the beam, dealing 4 damage.
• Shoots the beam, dealing 4 damage.
• Charges the beam, increasing its strength to 8.

In that case the program deals 9 damage in total.

The universe's top algorithmists built a shield that withstands at most a total of $D$ damage. The robot's current program may deal more damage than that when it runs.

The President of the Universe will fly into space and hack the program before the robot runs it. The only hack the President can perform without the robot noticing is swapping two adjacent instructions. For example, swapping the third and fourth instructions of the program above gives SCSCSC, which reduces the total damage to 7. Hacking again to get SCSSCC reduces it to 5.

The President does not want to hack too many times. Find the smallest number of hacks that makes the program deal at most $D$ total damage. If it is impossible, report that.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains an integer $D$, the maximum total damage the shield can withstand, and a string $P$, the robot's program.

For each test case, print one line Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the minimum number of hacks needed, or IMPOSSIBLE if no number of hacks works.

• $1 \le T \le 100$
• $1 \le D \le 10^9$
• $2 \le$ length of $P \le 30$
• Every character in $P$ is C or S.

The last three sample cases do not appear in test set 1.

In Sample Case #1, the President can swap the two instructions and reduce the total damage to 1, which the shield can withstand.

In Sample Case #2, no hack is needed, since the 2 total damage already fits within the shield.

In Sample Case #3, the program deals more damage than the shield can withstand, and hacking cannot change that. The universe is doomed.

Sample Case #4 uses the program from the problem statement. Two hacks reduce the damage to 5. One hack cannot reduce it to 6 or less, since the President can only swap adjacent instructions.

In Sample Case #5, the robot never shoots, so it never deals damage. No hacking is required.

In Sample Case #6, five hacks are required. Two hacks that swap the same pair of positions still count as separate hacks.