DPUM - Desafio 2

És o cozinheiro chefe de serviço no melhor restaurante de panquecas do mundo. As panquecas são cozinhadas numa fila única sobre uma superficie quente.
Como parte dos esforços infinitos para maximizar a eficiência, recentemente a Casa decidiu dar-te uma espátula enorme que vira exatamente K panquecas consecutivas, ou seja, nesse intervalo de K panquecas, ele muda o lado com a cara sorridente para um lado sem nada e vice versa. Não muda a ordem da esquerda para a direita das panquecas.

Não é possível virar menos de K panquecas de cada vez com a espátula , mesmo que seja no fim da linha (existem duas fronteiras na superfície de cozedura. Por exemplo, podes virar as primeiras K panquecas, mas não as primeiras K-1 panquecas.

O teu aprendiz, que ainda está a aprender a trabalhar, usou a espátula antiquada, que só vira uma panqueca de cada vez, para virar algumas panquecas e depois correu até a casa de banho com ela, mesmo antes de os clientes chegarem para visitar a cozinha. Tu só tens a espátula enorme, e precisas de a usar para rapidamente virares todas as panquecas para o lado com a cara sorridente, para que os clientes saiam felizes com a sua visita.

Dado o estado atual das panquecas, calcula o número mínimo de usos da espátula enorme que são necessários para deixar todas as panquecas do lado da cara sorridente ou dizer que não é possível.
INPUT:

A primeira linha do input dá o número de casos de teste, T.

Seguem os T casos de teste. Cada um consiste de uma linha com uma string S e um integer K. S representa a fila de panquecas: cada um dos seus caracteres ou é um + (que representa a panqueca que está inicialmente do lado com a cara sorridente) ou - (que representa a panqueca que está inicialmente do lado sem nada).

OUTPUT:

Para cada caso teste, devolver uma linha que contem Case#x: y, onde x é o número do caso teste (começando em 1) e y ou é IMPOSSIBLE se não existir nenhuma maneira de ter todas as panquecas com o lado feliz para cima, ou um integer que representa o número mínimo de vezes que é necessário usar a espátula enorme para o fazer.

EXEMPLO:


INPUT:
3
---+-++- 3
+++++ 4
-+-+- 4

OUTPUT:

Case #1: 3

Case#2: 0

Case#3: IMPOSSIBLE

No Case#1 é possível que todas as panquecas fiquem do lado com a cara sorridente virando apenas as 3 panquecas do lado mais a esquerda, chegando a ++++-++-, depois as 3 panquecas mais a direita, chegando a ++++---+ e finalmente as 3 panquecas que restam com o lado sem nada virado para cima. Existem outras maneiras de o fazer virando 3 vezes ou mais, mas nunca virando menos de 3 vezes.
No Case #2, todas as panquecas já estão viradas para o lado com a cara sorridente, então não existe necessidade de virar nenhuma.
No Case #3, não existe nenhuma maneira de fazer com que a segunda e a terceira panquecas (a contar da esquerda) fiquem com o mesmo lado para cima, porque quando as tentamos virar ambas viram. Assim, é impossivel que todas as panquecas fiquem do lado feliz para cima.