弹珠游戏(2021 CoE-I C)

题目描述

$\operatorname{Alice}$ 对弹珠游戏已经有些厌烦了,她经常在电脑上玩这个游戏。她之所以感到厌烦是因为在这个游戏上她已经是专家级别,她总是能够和电脑打成平手。$\operatorname{Bob}$ 为 $\operatorname{Alice}$ 创造了一款新的电脑游戏。以下是这款两人电脑游戏的规则: (1)游戏在如下图所示的菱形棋盘上进行; ![](https://cdn.luogu.com.cn/upload/image_hosting/qw7lsky0.png) (2)两名玩家轮流放置弹珠,可以在横向、纵向、$45$ 度斜线、$135$ 度斜线方向未放置弹珠的位置**连续放置 $1$ 至 $3$ 颗弹珠**,玩家在可以放置弹珠的情况下,必须至少放置 $1$ 颗弹珠。以下是合法的单次放置操作的示例(黑色圆点表示放置了弹珠,白色圆点表示未放置弹珠,进行该次操作前棋盘为空): ![](https://cdn.luogu.com.cn/upload/image_hosting/v38tajmr.png) 以下是非法的单次放置操作的示例(黑色圆点表示放置了弹珠,白色圆点表示未放置弹珠,进行该次操作前棋盘为空): ![](https://cdn.luogu.com.cn/upload/image_hosting/mldg0cs0.png) 非法原因的解释:($a$)三颗弹珠不在同一条斜线(或者垂直线)上;($b$)两颗弹珠之间相隔一个空位;($c$)三颗弹珠不在同一条斜线上;($d$)三颗弹珠不在同一条斜线(或者垂直线)上;($e$)一次性放置了 $4$ 颗弹珠;($f$)三颗弹珠不在同一条水平线(或者垂直线、或者斜线)上。 (3)如果某位玩家无法再继续放置弹珠,则该名玩家输掉游戏,另外一名玩家获胜。 $\operatorname{Alice}$ 总是第一个进行游戏,而且经常是和 $\operatorname{Bob}$ 玩这个游戏,$\operatorname{Bob}$ 在进行若干游戏操作后可能会离开,将游戏交由电脑代理,电脑总是按照最优策略放置弹珠。 给定 $\operatorname{Bob}$ 离开后的游戏状态,你的任务是确定 $\operatorname{Alice}$ 是否可能在对阵电脑时获得胜利。

输入输出格式

输入格式


**输入包含多组测试数据**。 输入第一行包含一个整数 $T$,表示测试数据的组数。接着是一个空行。再接下来是 $T$ 组表示棋盘状态的数据,每组数据由七行字符构成,表示 $\operatorname{Bob}$ 离开后的游戏状态,`*` 表示该位置已经放置了弹珠,`.` 表示该位置未放置弹珠。相邻两组测试数据之间有一个空行。

输出格式


对于每组测试数据,如果 $\operatorname{Alice}$ 能够获胜,输出 `Possible.`,否则输出 `Impossible.`。

输入输出样例

输入样例 #1

6

   *
  * *
 * * *
* * * *
 . * *
  . *
   .

   *
  * *
 * * *
. . . *
 * * *
  * *
   *

   *
  * *
 * * .
* * * *
 * * .
  * *
   *

   *
  * *
 . . *
* * * *
 * * *
  * *
   *

   .
  * *
 * * *
* * * .
 * * *
  * *
   *

   .
  * .
 * * .
* * * .
 * * *
  * *
   *

输出样例 #1

Possible.
Possible.
Possible.
Possible.
Impossible.
Possible.

说明

#### 样例说明 第一组数据,$\operatorname{Alice}$ 可以选择在棋盘左下角的斜线方向所剩下的 $3$ 个空余位置一次性连续放置 $3$ 颗弹珠,使得后续电脑无法再放置弹珠,因此 $\operatorname{Alice}$ 能够获胜。 第二组数据,$\operatorname{Alice}$ 可以选择沿着第四行剩下的 $3$ 个空余位置一次性连续放置 $3$ 颗弹珠,使得后续电脑无法再放置弹珠,因此 $\operatorname{Alice}$ 能够获胜。 第三组数据,棋盘剩下倒数第二列两个连续的空余位置,$\operatorname{Alice}$ 可以一次放置 $2$ 颗弹珠,使得后续电脑无法放置弹珠,因此 $\operatorname{Alice}$ 会获胜。 第四组数据,类似于第二组测试数据,棋盘剩下第三行两个连续的空余位置,因此 $\operatorname{Alice}$ 会获胜。 第五组数据,棋盘只剩下两个不连续的空余位置,由于 $\operatorname{Alice}$ 一次只能选择一个空余位置放置 $1$ 颗弹珠,因此不管 $\operatorname{Alice}$ 如何操作,电脑总能一次性将剩下的棋盘使用弹珠填满,使得 $\operatorname{Alice}$ 无法再继续放置弹珠,因此 $\operatorname{Alice}$ 会输掉比赛。 第六组数据,$\operatorname{Alice}$ 可以选择在棋盘右上角斜线方向的中间两个空余位置放置 $2$ 颗弹珠,使得棋盘状态转化为样例输入的第五组数据,因此 $\operatorname{Alice}$ 会赢得比赛。 ------------ #### 数据范围 对于 $10\%$ 的数据,$0 \lt T \leq 10$。 对于 $60\%$ 的数据,$0 \lt T \leq 10^3$。 对于 $80\%$ 的数据,$0 \lt T \leq 10^5$。 对于 $100\%$ 的数据,$0 \lt T \leq 10^6$。 ------------ #### 提示 本题输入量较大,请使用合适的读入方式。