초대형 팬케이크 뒤집개 (Large)

어느 가게에서 새로운 팬케이크를 내놓았다. 한쪽 면에는 초콜릿 칩으로 웃는 얼굴이 그려져 있고(웃는 면), 반대쪽 면에는 아무것도 없다(빈 면).

너는 주방장이다. 팬케이크는 뜨거운 철판 위에 한 줄로 놓여 구워지고 있다. 가게는 효율을 높이려고 연속한 $K$개를 한 번에 뒤집는 초대형 뒤집개를 새로 들여놓았다. 이 뒤집개를 쓰면 그 $K$개 구간 안에서 웃는 면이 위인 팬케이크는 빈 면이 위가 되고, 빈 면이 위인 팬케이크는 웃는 면이 위가 된다. 팬케이크의 좌우 순서는 바뀌지 않는다.

철판 양옆에 턱이 있어서 줄의 끝에서도 $K$개보다 적게 뒤집을 수는 없다. 예를 들어 맨 왼쪽 $K$개는 뒤집을 수 있지만 맨 왼쪽 $K - 1$개는 뒤집을 수 없다.

아직 일이 서툰 견습 요리사가 한 장씩 뒤집는 옛날 뒤집개로 몇 장을 뒤집어 놓고는, 그 뒤집개를 든 채 자리를 비웠다. 손님이 주방을 구경하러 오기 직전이다. 남은 도구는 초대형 뒤집개뿐이고, 모든 팬케이크가 웃는 면이 위를 향하도록 서둘러 맞춰야 한다.

팬케이크의 현재 상태가 주어진다. 모든 팬케이크를 웃는 면이 위로 향하게 만드는 데 필요한 초대형 뒤집개 사용 횟수의 최솟값을 구하여라. 그렇게 만들 방법이 없으면 없다고 답한다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 다음 $T$개의 줄에 각각 문자열 $S$와 정수 $K$가 공백으로 구분되어 주어진다. $S$는 팬케이크가 놓인 줄을 나타내고, 각 문자는 처음에 웃는 면이 위인 팬케이크를 뜻하는 + 또는 처음에 빈 면이 위인 팬케이크를 뜻하는 - 중 하나이다.

제한

• $1 \le T \le 100$
• $S$의 모든 문자는 + 또는 -이다.
• $2 \le K \le |S|$
• $2 \le |S| \le 1000$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이다. $y$는 모든 팬케이크를 웃는 면이 위로 만들 방법이 없으면 IMPOSSIBLE이고, 방법이 있으면 초대형 뒤집개를 사용해야 하는 최소 횟수이다.

$S$가 ---+-++-이고 $K = 3$이면 먼저 왼쪽 끝 3개를 뒤집어 ++++-++-를 만들고, 그다음 오른쪽 끝 3개를 뒤집어 ++++---+를 만든 뒤, 남아 있는 빈 면 3개를 뒤집으면 모두 웃는 면이 위가 된다. 3번으로 끝내는 다른 방법도 있지만 2번 이하로는 불가능하다.

$S$가 +++++이고 $K = 4$이면 이미 모두 웃는 면이 위이므로 한 번도 뒤집지 않는다.

$S$가 -+-+-이고 $K = 4$이면 어떤 뒤집기를 해도 왼쪽에서 두 번째와 세 번째 팬케이크가 항상 함께 뒤집힌다. 두 팬케이크는 서로 다른 면이 위인 채로 시작하므로 같은 면을 위로 만들 수 없고, 따라서 모두 웃는 면이 위가 되게 할 방법이 없다.