Oversized Pancake Flipper (Small)

Last year the Infinite House of Pancakes introduced a new kind of pancake. It has a happy face made of chocolate chips on one side (the happy side) and nothing on the other side (the blank side).

You are the head cook on duty. The pancakes are cooked in a single row over a hot surface. As part of its infinite efforts to maximize efficiency, the House has recently given you an oversized pancake flipper that flips exactly K consecutive pancakes. Within that range of K pancakes it changes every happy side pancake to a blank side pancake and every blank side pancake to a happy side pancake. It does not change the left to right order of those 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 you cannot flip the leftmost K - 1 pancakes.

Your apprentice cook, who is still learning the job, used the old fashioned single pancake flipper to flip some individual pancakes and then ran to the restroom with it, right before the time when customers come to visit the kitchen. Only the oversized flipper is left, and you need to use it quickly so that every cooking pancake ends up happy side up and the customers leave feeling happy with their visit.

Given the current state of the pancakes, compute the minimum number of uses of the oversized pancake flipper needed to leave all pancakes happy side up, or report that there is no way to do it.

The first line of the input gives the number of test cases, T. T test cases follow. Each consists of one line with a string S and an integer K, separated by a space. S represents the row of pancakes. Each character of S is either +, which represents a pancake that is initially happy side up, or -, which represents a pancake that is initially blank side up.

Limits

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

For each test case, output one line containing Case #x: y, where x is the test case number starting from 1. y is IMPOSSIBLE if there is no way to get all the pancakes happy side up, and otherwise the minimum number of times you need to use the oversized pancake flipper.

In the first test case of example 1 you can flip the leftmost 3 pancakes of ---+-++- to get ++++-++-, then the rightmost 3 to get ++++---+, and then the 3 pancakes that remain blank side up. Other ways need 3 flips or more, and none needs fewer than 3.

In the second test case all of the pancakes are already happy side up, so no flip is needed.

In the third test case every flip flips the second and the third pancake from the left together, so their upper sides can never be made equal. There is therefore no way to make all of the pancakes happy side up.