Wormly
Джонли разрабатывает свою первую компьютерную игру. В начальной сцене главный герой, Червякли, должен пересечь мост под названием Мостли. Червякли — это червяк, состоящий из b одинаковых круглых пузырей и l ног. Каждая нога должна находиться под одним из пузырей, и под каждым пузырем может быть не более одной ноги. Мостли изначально должен был состоять из n досок, каждая из которых имеет ширину, равную диаметру пузыря Червякли. Однако некоторые доски отсутствуют.
Червякли может выполнять одно из следующих действий:
Переместить одну из ног вперед через любое количество (возможно, отсутствующих) досок. После перемещения нога должна оказаться на доске и под одним из пузырей Червякли. Нога не может обгонять другие ноги.
Переместить все пузыри вперед на одну доску, при этом ноги остаются на тех же досках. После перемещения каждая нога должна оставаться под одним из пузырей Червякли.
В этом примере единственное возможное перемещение для последней ноги — это позиция b. (Доска в позиции a отсутствует, поэтому нога не может туда переместиться. Чтобы попасть в позицию c, последняя нога должна была бы обогнать первую ногу.) Также в этом примере перемещение всех пузырей вперед невозможно, потому что последняя нога Червякли останется без пузыря над ней.
Джонли хочет узнать, сколько времени займет анимация, пока Червякли не достигнет конца Мостли. Изначально пузыри Червякли находятся прямо над самыми левыми b досками моста, а его ноги — на самых левых l досках. В конце анимации пузыри Червякли должны находиться прямо над самыми правыми b досками, а его ноги — на самых правых l досках. Самые левые и правые l доски Мостли не отсутствуют.
Входные данные
На первой строке дано положительное целое число: количество тестов, не более 100. Далее для каждого теста:
Одна строка с тремя целыми числами l, b и n (1 ≤ l ≤ b ≤ n ≤ 1 000 000): количество ног, количество пузырей и длина моста соответственно.
Одна строка, содержащая n символов, либо '0', либо '1', описывающая Мостли. Единица обозначает доску, а ноль обозначает отсутствующую доску.
Выходные данные
Для каждого теста:
Одна строка с целым числом: минимальное количество шагов, необходимых Червякли, чтобы пересечь Мостли. Если невозможно пересечь мост, соблюдая ограничения, строка должна содержать "IMPOSSIBLE" вместо этого.