В прошлом году Бесконечный Дом Блинчиков представил новый вид блинов. Блин имеет счастливое лицо из шоколадной стружки с одной стороны ("счастливая сторона") и ничего с другой стороны ("пустая сторона").

Сегодня Вы главный дежурный повар. Блины готовятся в один ряд на горячей поверхности. В рамках своих бесконечных усилий по максимизации эффективности, Дом Блинчиков недавно предоставил Вам крупногабаритный флиппер для блинов, который переворачивает ровно k последовательных блинов. То есть для последовательно расположенных k блинов он заменяет каждый блин счастливой стороны блином пустой стороны, и наоборот. При этом порядок блинов слева направо не меняется.

Вы не можете переворачивать с помощью флиппера менее k блинов за раз, даже на конце ряда (поскольку на обеих сторонах варочной поверхности имеются выпуклые края). Например, вы можете перевернуть первые k блинов, но не первые k - 1 блинов.

Ваш ученик-повар, который все еще изучает работу, просто использовал старомодный флиппер для одного блинчика, чтобы перевернуть несколько отдельных блинов, а затем побежал с ним в туалет, как раз перед тем, как клиенты начали приходить на кухню. У Вас остался только негабаритный флиппер для блинов. Вам нужно быстро его использовать, чтобы все блины были перевернуты счастливой стороной. Тогда клиенты останутся довольны своим визитом.

По заданному состоянию блинов подсчитайте минимальное количество использований негабаритного флиппера для блинов, необходимых для переворачивания всех блинов счастливой стороной вверх, или укажите, что сделать это невозможно.

Входные данные

Первая строка содержит количество тестов t (1 ≤ t ≤ 100). Далее следуют t тестов. Каждый тест содержит одну строку s и целое число k (2 ≤ k ≤ длина s). s задает строку блинов: каждый символ равен или + (блин лежит счастливой стороной вверх) или - (блин лежит пустой стороной вверх).

Выходные данные

Для каждого теста вывести строку содержащую Case #x: y, где x номер теста (начиная с 1) и y либо IMPOSSIBLE если невозможно перевернуть все блины счастливой стороной вверх, либо число - наименьшее количество раз применения флиппера для достижения цели.