Mcdonald’s has introduced a new kind of burger. It has a smiley face made of potato chips on one side (the “smiley”), and nothing on the other side (the “sad”).
You are the head cook on duty. The burgers are cooked in a single row over a hot surface. As part of its infinite efforts to maximize efficiency, Mcdonald’s has recently given you an oversized burger flipper that flips exactly K consecutive burgers.
That is, in that range of K burgers, it changes every smiley-side burger to a sad-side burger, and vice versa; it does not change the left-to-right order of those burgers.
You cannot flip fewer than K burgers at a time with the flipper, even at the ends of the row (since there are raised borders on both sides of the cooking surface).
For example, you can flip the first K burgers, but not the first K - 1 burgers.
Your apprentice cook, who is still learning the job, just used the old-fashioned single-burger flipper to flip some individual burgers and then ran to the restroom with it, right before the time when customers come to visit the kitchen.
You only have the oversized burger flipper left, and you need to use it quickly to leave all the cooking burgers smiley side up, so that the customers leave feeling happy with their visit.
Given the current state of the burgers, calculate the minimum number of uses of the oversized burger flipper needed to leave all burgers smiley side up, or state that there is no way to do it.
Constraints →
1 ≤ T ≤ 100.
2 ≤ K ≤ length of S.
2 ≤ length of S ≤ 1000.
Input →
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. S represents the row of burgers: each of its characters is either + (which represents a burger that is initially smiley side up) or - (which represents a burger that is initially sad side up).
Output →
Print the output one line containing Case #x: y, where x is the test case number (starting from 1) and y is either IMPOSSIBLE if there is no way to get all the burgers smiley side up, or an integer representing the the minimum number of times you will need to use the oversized burger flipper to do it.
LOGICAL TEST CASE 1 →
Input =
4
—±+++4
+±±+±3
—++±+3
++±-±+4
Output =
Case #1: 4
Case #2: 3
Case #3: 3
Case #4: 3