Lật bánh

flipCake.cpp / Timelimit: 1s

Trong kì nghỉ hè, An đăng ký vào một lớp học nấu ăn. Biết An là một người giỏi tin học, bếp trưởng Chef đố An một câu đố: Trên chảo có ~n~ chiếc bánh đang nướng, mỗi chiếc bánh đều có 2 mặt trong đó một mặt chín (~kí hiệu ‘+’~) và một mặt chưa chín (~kí hiệu ‘-‘~). Mỗi lần lật bánh An chỉ được lật chính xác ~k~ chiếc bánh liên tiếp nhau. Bếp trưởng Chef muốn biết số lần lật bánh ít nhất để ngửa tất cả các mặt đã chín lên trên hoặc cho Chef biết không có cách nào để lật ngửa tất cả các mặt chín lên. Mỗi lần lật bánh, mặt ngửa lên của chiếc bánh sẽ thay đổi (chín thành chưa chín và ngược lại)

Input

• Dòng đầu tiên số nguyên ~T~ là số bộ test
• Dòng thứ 2 chứa xâu ~S~ chỉ chứa kí tự ‘+’ (tương ứng với mặt chín) hoặc ‘-‘
• (tương ứng với mặt chưa chín) và số nguyên ~k~

Output

• ~T~ dòng là kết quả của bài toán, số lần cần lật ít nhất hoặc là nếu không có
• Cách nào in ra “IMPOSSIBLE”

Sample Input 1

flipCake.inp flipCake.out
3 3
---+-++- 3 0
+++++ 4 IMPOSSIBLE
-+-+- 4
Sub1 (40% ): 1≤T≤20, |S| ≤10, k≤|S|
Sub2 (60% ) :1< T≤20, |S| ≤1000, k≤|S|