Oversized Pancake Flipper (Large)

A pancake house introduced a new kind of pancake. One side has a happy face made of chocolate chips (the happy side), and the other side has nothing on it (the blank side).

You are the head cook on duty. The pancakes cook in a single row on a hot surface. To work faster, the house has bought an oversized pancake flipper that flips exactly $K$ consecutive pancakes at once. Inside that range of $K$ pancakes it turns every happy side up pancake blank side up and every blank side up pancake happy side up. It does not change the left to right order of the pancakes.

Raised borders run along both sides of the cooking surface, so you cannot flip fewer than $K$ pancakes at a time, not even at the ends of the row. For example, you can flip the leftmost $K$ pancakes, but not the leftmost $K - 1$ pancakes.

Your apprentice cook, who is still learning the job, used the old single pancake flipper to turn over some individual pancakes and then walked off with it. Customers are about to visit the kitchen. The oversized flipper is the only tool left, and every pancake has to end up happy side up.

Given the current state of the pancakes, compute the minimum number of uses of the oversized pancake flipper that leaves every pancake happy side up, or report that no sequence of uses does it.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains a string $S$ and an integer $K$, separated by a space. $S$ describes the row of pancakes. Each of its characters is either +, a pancake that starts happy side up, or -, a pancake that starts blank side up.

Limits

• $1 \le T \le 100$
• Every character of $S$ is either + or -.
• $2 \le K \le |S|$
• $2 \le |S| \le 1000$

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1. $y$ is IMPOSSIBLE when no sequence of flips leaves every pancake happy side up, and otherwise the minimum number of times the oversized flipper has to be used.

When $S$ is ---+-++- and $K = 3$, flip the leftmost 3 pancakes to reach ++++-++-, then the rightmost 3 to reach ++++---+, then the 3 pancakes that are still blank side up. Other sequences also finish in 3 flips, and none finishes in 2 or fewer.

When $S$ is +++++ and $K = 4$, every pancake is already happy side up, so no flip is needed.

When $S$ is -+-+- and $K = 4$, every legal flip covers both the second and the third pancake from the left, so those two always turn together. They start on opposite sides, so they can never show the same side, and no sequence of flips leaves the whole row happy side up.