Năm ngoái, Infinite House of Pancakes giới thiệu một loại bánh mới: một mặt có khuôn mặt vui bằng hạt sô-cô-la (“mặt vui”), mặt kia không có gì (“mặt trắng”).

Bạn là bếp trưởng trực ca. Bánh được nướng thành một hàng trên bề mặt nóng. Để tiếp tục nâng cao hiệu suất, nhà hàng cấp cho bạn một xẻng lật quá khổ, mỗi lần lật đúng \(K\) chiếc bánh liên tiếp. Trong đoạn ấy, mọi bánh đang ngửa mặt vui sẽ thành mặt trắng và ngược lại; thứ tự trái sang phải của bánh không đổi.

Bạn không thể dùng xẻng để lật ít hơn \(K\) chiếc, kể cả ở hai đầu hàng vì bề mặt nướng có gờ cao hai bên. Chẳng hạn, có thể lật \(K\) chiếc đầu tiên nhưng không thể lật chỉ \(K-1\) chiếc đầu.

Người học việc vừa dùng xẻng loại cũ để lật riêng một số bánh rồi mang xẻng ấy vào nhà vệ sinh, ngay trước lúc khách tham quan bếp. Bạn chỉ còn xẻng quá khổ và cần nhanh chóng làm mọi chiếc bánh ngửa mặt vui để khách ra về vui vẻ.

Biết trạng thái hiện tại, hãy tính số lần dùng xẻng ít nhất để tất cả bánh ngửa mặt vui, hoặc cho biết điều đó là không thể.

Dữ liệu vào

Dòng đầu chứa số test \(T\). Mỗi test gồm một dòng chứa chuỗi \(S\) và số nguyên \(K\). Chuỗi \(S\) biểu diễn hàng bánh: + là bánh ban đầu ngửa mặt vui, - là bánh ban đầu ngửa mặt trắng.

Dữ liệu ra

Với mỗi test, in Case #x: y, trong đó x là số thứ tự test bắt đầu từ 1; y là IMPOSSIBLE nếu không thể làm mọi bánh ngửa mặt vui, hoặc là số lần dùng xẻng ít nhất.

Ràng buộc

• \(1\le T\le100\).
• Mỗi ký tự của \(S\) là + hoặc -.
• \(2\le K\le |S|\).

Phân nhóm

• Test Set 1 (Visible): \(2\le |S|\le10\).
• Test Set 2 (Hidden): \(2\le |S|\le1000\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
---+-++- 3
+++++ 4
-+-+- 4

Case #1: 3
Case #2: 0
Case #3: IMPOSSIBLE

Nguồn

Google Code Jam 2017, Vòng loại, bài Oversized Pancake Flipper.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.