Description

去年，Infinite House of Pancakes 推出了一种新型煎饼。这种煎饼的一面（“开心面”）上有用巧克力豆做成的笑脸，另一面（“空白面”）则什么都没有。

你是当班的主厨。煎饼被排成一排在加热面上烹饪。为了进一步提升效率，餐厅最近给你配备了一个超大号煎饼翻转器，每次可以同时翻转恰好 $K$ 个连续的煎饼。也就是说，在这 $K$ 个煎饼的范围内，每个开心面朝上的煎饼会变为空白面朝上，反之亦然；煎饼的左右顺序不会改变。

你不能用翻转器翻转少于 $K$ 个煎饼，即使是在煎饼排的两端（因为加热面两侧有凸起的边界）。例如，你可以翻转最左边的 $K$ 个煎饼，但不能只翻转最左边的 $K-1$ 个煎饼。

你的学徒厨师还在学习工作，他刚刚用老式的单煎饼翻转器翻转了一些单独的煎饼，然后带着翻转器跑去洗手间了，正好在顾客即将参观厨房之前。现在你只剩下超大号煎饼翻转器，你需要尽快使用它，使所有正在烹饪的煎饼都开心面朝上，这样顾客才能满意地离开。

给定当前煎饼的状态，计算至少需要使用多少次超大号煎饼翻转器，才能让所有煎饼都开心面朝上；或者说明无法做到这一点。

Input Format

输入的第一行包含测试用例的数量 $T$。接下来有 $T$ 组测试用例。每组测试用例包含一行，包括一个字符串 $S$ 和一个整数 $K$。$S$ 表示煎饼的排列：每个字符为 +（表示该煎饼初始为开心面朝上）或 -（表示该煎饼初始为空白面朝上）。

Output Format

对于每组测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是所需使用超大号煎饼翻转器的最小次数，或者如果无法做到则输出 IMPOSSIBLE。

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

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

Hint

样例解释

• 对于第 1 组测试用例，你可以先翻转最左边的 3 个煎饼，变为 ++++-++-，然后翻转最右边的 3 个，变为 ++++---+，最后再翻转剩下的 3 个空白面朝上的煎饼。还有其他方法可以用 3 次或更多次翻转完成，但没有比 3 次更少的方案。

• 对于第 2 组测试用例，所有煎饼已经全部开心面朝上，因此不需要翻转。

• 对于第 3 组测试用例，无法让从左数第 2 和第 3 个煎饼都朝同一面，因为任何一次翻转都会同时翻转它们。因此无法让所有煎饼都开心面朝上。

数据范围

• $1 \leq T \leq 100$。
• $S$ 中每个字符均为 + 或 -。
• $2 \leq K \leq S$ 的长度。

小数据集（5 分，测试集 1 - 可见）

• $2 \leq S$ 的长度 $\leq 10$。

大数据集（10 分，测试集 2 - 隐藏）

• $2 \leq S$ 的长度 $\leq 1000$。

由 ChatGPT 4.1 翻译