초대형 팬케이크 뒤집개

작년에 무한 팬케이크 하우스는 새로운 종류의 팬케이크를 선보였다. 한쪽 면에는 초콜릿 칩으로 만든 웃는 얼굴이 있고(이 면을 "웃는 면"이라고 한다), 다른 쪽 면에는 아무것도 없다(이 면을 "빈 면"이라고 한다).

당신은 당번 수석 요리사이다. 팬케이크들은 뜨거운 조리대 위에서 한 줄로 조리된다. 효율을 극대화하려는 하우스의 무한한 노력의 일환으로, 최근 당신에게 연속한 정확히 K개의 팬케이크를 뒤집는 초대형 팬케이크 뒤집개가 지급되었다. 즉, 해당 범위의 K개 팬케이크에서 웃는 면이 위를 향한 모든 팬케이크를 빈 면이 위를 향하도록 바꾸고, 그 반대도 마찬가지로 바꾼다. 이때 팬케이크들의 왼쪽에서 오른쪽으로의 순서는 바뀌지 않는다.

줄의 양 끝에서도 뒤집개로 한 번에 K개보다 적은 팬케이크를 뒤집을 수 없다(조리대 양쪽에 솟아 있는 테두리가 있기 때문이다). 예를 들어, 맨 앞의 K개 팬케이크는 뒤집을 수 있지만, 맨 앞의 K - 1개 팬케이크는 뒤집을 수 없다.

아직 일을 배우고 있는 견습 요리사가 구식의 팬케이크 한 개용 뒤집개로 몇몇 팬케이크를 개별적으로 뒤집은 뒤, 손님들이 주방을 방문하러 오기 직전에 그 뒤집개를 들고 화장실로 달려갔다. 이제 당신에게는 초대형 팬케이크 뒤집개만 남아 있으며, 손님들이 방문에 만족하며 떠날 수 있도록 이를 빠르게 사용해 조리 중인 모든 팬케이크의 웃는 면이 위를 향하게 해야 한다.

팬케이크들의 현재 상태가 주어질 때, 모든 팬케이크의 웃는 면이 위를 향하게 하는 데 필요한 초대형 팬케이크 뒤집개의 최소 사용 횟수를 계산하거나, 그렇게 할 방법이 없음을 밝혀라.

제한

시간 제한: 테스트 세트당 20초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. S의 모든 문자는 + 또는 -이다. 2 ≤ K ≤ S의 길이.

작은 데이터 세트(테스트 세트 1 - 공개)

2 ≤ S의 길이 ≤ 10.

큰 데이터 세트(테스트 세트 2 - 비공개)

2 ≤ S의 길이 ≤ 1000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 문자열 S와 정수 K가 한 줄에 주어진다. S는 팬케이크들이 놓인 줄을 나타낸다. S의 각 문자는 +(처음에 웃는 면이 위를 향한 팬케이크를 나타낸다) 또는 -(처음에 빈 면이 위를 향한 팬케이크를 나타낸다)이다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 (1부터 시작하는) 테스트 케이스 번호이며, y은 모든 팬케이크의 웃는 면이 위를 향하게 할 방법이 없다면 IMPOSSIBLE이고, 그렇지 않으면 그렇게 하기 위해 초대형 팬케이크 뒤집개를 사용해야 하는 최소 횟수를 나타내는 정수이다.

케이스 #1에서는 먼저 가장 왼쪽의 3개 팬케이크를 뒤집어 ++++-++-로 만든 다음, 가장 오른쪽의 3개를 뒤집어 ++++---+로 만들고, 마지막으로 빈 면이 위를 향한 채 남아 있는 3개 팬케이크를 뒤집으면 모든 팬케이크의 웃는 면이 위를 향하게 할 수 있다. 3번 이상 뒤집어서 그렇게 하는 다른 방법들도 있지만, 3번보다 적게 뒤집는 방법은 없다.

케이스 #2에서는 모든 팬케이크의 웃는 면이 이미 위를 향하고 있으므로, 어떤 팬케이크도 뒤집을 필요가 없다.

케이스 #3에서는 어떤 뒤집기든 왼쪽에서 두 번째와 세 번째 팬케이크를 모두 뒤집기 때문에, 두 팬케이크가 같은 면을 위로 향하게 할 방법이 없다. 따라서 모든 팬케이크의 웃는 면이 위를 향하게 할 방법이 없다.