The Infinite House of Dosa introduced a new kind of dosa. 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 Dosa 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 dosa flipper that flips exactly K consecutive Dosa. That is, in that range of K Dosa, it changes every happy-side dosa to a blank-side dosa, and vice versa; it does not change the left-to-right order of those Dosa. You cannot flip fewer than K Dosa 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 Dosa, but not the first K - 1 Dosa. Your apprentice cook, who is still learning the job, just used the old-fashioned single-dosa flipper to flip some individual Dosa and then ran to the restroom with it, right before the time when customers come to visit the kitchen. You only have the oversized dosa flipper left, and you need to use it quickly to leave all the cooking Dosa happy side up, so that the customers leave feeling happy with their visit. Given the current state of the Dosa, calculate the minimum number of uses of the oversized dosa flipper needed to leave all Dosa happy side up, or state that there is no way to do it.
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 Dosa: each of its characters is either + (which represents a dosa that is initially happy side up) or - (which represents a dosa that is initially blank side up).
Output
For each test case, output one line containing y, where y is either IMPOSSIBLE if there is no way to get all the Dosa happy side up, or an integer representing the the minimum number of times you will need to use the oversized dosa flipper to do it.
Limits
1 ≤ T ≤ 100.
Every character in S is either + or -.
0 ≤ K ≤ length of S.
In Case #1, you can get all the Dosa happy side up by first flipping the leftmost 3 Dosa, getting to ++++-++-, then the rightmost 3, getting to ++++---+, and finally the 3 Dosa that remain blank side up. There are other ways to do it with 3 flips or more, but none with fewer than 3 flips. In Case #2, all of the Dosa are already happy side up, so there is no need to flip any of them. In Case #3, there is no way to make the second and third Dosa from the left have the same side up, because any flip flips them both. Therefore, there is no way to make all of the Dosa happy side up.