Великогабаритний фліппер для млинців
У минулому році Безкінечний Дім Млинців представив новий вид млинців. Кожен млинець має щасливе обличчя з шоколадної стружки з одного боку ("щаслива сторона") і нічого з іншого боку ("порожня сторона").
Сьогодні ви головний черговий кухар. Млинці викладені в один ряд на гарячій поверхні. У своїх безкінечних зусиллях з підвищення ефективності, Дім Млинців надав вам великогабаритний фліппер для млинців, який перевертає рівно k послідовних млинців. Це означає, що для k послідовно розташованих млинців він змінює кожен млинець щасливої сторони на млинець порожньої сторони, і навпаки. При цьому порядок млинців зліва направо залишається незмінним.
Ви не можете перевертати менше ніж k млинців за раз, навіть якщо це кінець рядка (оскільки на обох сторонах варильної поверхні є випуклі краї). Наприклад, ви можете перевернути перші k млинців, але не перші k - 1 млинців.
Ваш учень-кухар, який ще вчиться, щойно використав старомодний фліппер для одного млинця, щоб перевернути кілька окремих млинців, а потім побіг з ним до туалету, якраз перед тим, як клієнти почали приходити на кухню. У вас залишився лише великогабаритний фліппер для млинців. Вам потрібно швидко його використати, щоб усі млинці були перевернуті щасливою стороною вгору. Тоді клієнти залишаться задоволені своїм візитом.
За заданим станом млинців підрахуйте мінімальну кількість використань великогабаритного фліппера для млинців, необхідних для перевертання всіх млинців щасливою стороною вгору, або вкажіть, що зробити це неможливо.
Вхідні дані
Перша рядок містить кількість тестів t (1 ≤ t ≤ 100). Далі слідують t тестів. Кожен тест містить один рядок s і ціле число k (2 ≤ k ≤ довжина s). s задає рядок млинців: кожен символ дорівнює або + (млинець лежить щасливою стороною вгору) або - (млинець лежить порожньою стороною вгору).
Вихідні дані
Для кожного тесту виведіть рядок, що містить Case #x: y, де x - номер тесту (починаючи з 1) і y - або IMPOSSIBLE, якщо неможливо перевернути всі млинці щасливою стороною вгору, або число - найменша кількість разів застосування фліппера для досягнення мети.