Wormly#2458

Wormly

1 second
64 megabytes
Hard

Jonly is writing his first computer game. For the opening scene, he wants to have the main character, Wormly, cross Bridgely, the bridge. Wormly is a worm made of equal circular bubbles and legs. At all times, each leg has to be under one of the bubbles, and under each bubble there can be at most one leg. Bridgely was supposed to be composed of planks with the width of each plank equal to the diameter of each of Wormly's bubbles. However, some of the planks are missing.

At every moment, Wormly can do exactly one of the following:

In this example, the only possible move for the last leg is to position . (The plank at position is missing, so the leg cannot move there. To get to position , the last leg would have to overtake the first leg.) Also, in this example, moving all the bubbles forward is not allowed because Wormly's last leg would end up without a bubble over it.

Now Jonly is wondering how long the animation takes until Wormly reaches the end of Bridgely. Initially, Wormly's bubbles are directly above the leftmost planks of the bridge, and its legs are on the leftmost planks. At the end of the animation, Wormly's bubbles have to be directly above the rightmost planks, and its legs have to be on the rightmost planks. The leftmost and rightmost planks of Bridgely are not missing.

Input

On the first line, a positive integer: the number of test cases, at most . After that, for each test case:

  • One line with three integers , and (1 \leq l \leq b \leq n \leq 1\ 000\ 000): the number of legs, the number of bubbles, and the length of the bridge, respectively.

  • One line with a string consisting of characters, either '' or '', describing Bridgely. A one indicates a plank, and a zero indicates a missing plank.

Output

For each test case:

  • One line with an integer: the minimum number of steps it takes Wormly to cross Bridgely. If it is impossible to get across while satisfying the constraints, the line must contain IMPOSSIBLE instead.

Examples

Example 1

Loading
Loading