P16871 [GKS 2022 #A] Palindrome Free Strings

给定一个由字符 `0`、`1` 和 `?` 组成的字符串 $S$。你可以将每个 `?` 替换为 `0` 或 `1`。你的任务是判断是否可能为每个 `?` 赋值为 `0` 或 `1`，使得最终得到的字符串中不包含长度大于等于 $5$ 的回文子串。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。 每个测试用例由两行组成。 每个测试用例的第一行包含一个整数 $N$，表示字符串 $S$ 的长度。 每个测试用例的第二行包含一个长度为 $N$ 的字符串 $S$。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 为 `POSSIBLE`（如果存在一种赋值方式使得最终字符串没有长度大于等于 $5$ 的回文子串），否则为 `IMPOSSIBLE`。

在样例 #1 中，为了防止整个字符串成为回文，第一个和最后一个问号必须替换为不同的字符。 如果将第一个问号替换为 $0$，最后一个问号替换为 $1$，得到 $1000?1001$。如果剩下的 `?` 替换为 $1$，得到 $100011001$，此时前 $5$ 个字符构成一个长度为 $5$ 的回文。否则，得到 $100001001$，前 $6$ 个字符构成一个长度为 $6$ 的回文。 如果将第一个问号替换为 $1$，得到 $1001?0001$。如果剩下的 `?` 替换为 $1$，得到 $100110001$，此时后 $5$ 个字符构成一个长度为 $5$ 的回文。否则，得到 $100100001$，后 $6$ 个字符构成一个长度为 $6$ 的回文。 因此，无法得到合法字符串。 在样例 #2 中，一种将所有 `?` 替换后得到的合法字符串是 $10011$。 ### 限制条件 $1 \le T \le 100$。 $S$ 仅由字符 `0`、`1` 和 `?` 组成。 **测试集 1** $1 \le N \le 15$。 **测试集 2** $1 \le N \le 5 \times 10^4$。 翻译由 DeepSeek V4 Pro 完成