题目内容

手工课上，甲、乙轮流往一张九格纸盖章。甲先盖，章记作 $1$；乙后盖，章记作 $2$；还没盖的格子是 $0$。九格排成三行三列。

谁先让自己的章在同一行、同一列或同一条斜向上凑满三格，这一局立刻结束，对方不能再盖。每一格最多盖一次。两人每一步都挑对自己最终更有利的空格：优先让自己获胜，其次接受平局，最后才接受失败。

现在给出若干张已经盖过一部分的纸，判断每张按上面的规则收到结束时的结果。这些章必须能由「甲先手、一人一步、有人凑满就停」得到；否则这张纸无效。某人刚好用新盖的一章凑满三格，是正常收场，要报出胜负，不算无效。

输入描述

第一行一个整数 $t$，表示纸的张数。

接下来 $t$ 行。每行 $9$ 个整数，从左到右、再从上到下，是这一张纸的九格。

$1 \le t \le 200$。每一格只能是 $0$、$1$ 或 $2$。

输出描述

输出一行 $t$ 个整数，相邻两个之间用一个空格隔开，顺序和输入的纸张一致。

• $1$：甲最终获胜
• $2$：乙最终获胜
• $0$：双方都无法再获胜，以平局结束
• $-1$：这张纸无效

样例1

输入

2
1 1 0 2 2 0 0 0 0
2 2 0 1 1 0 1 0 0

输出

1 2

说明

第一张是

甲、乙各两枚，轮到甲。甲把第一行右侧盖成 $1$，第一行凑满，甲胜。甲若不盖这里，乙就能把第二行右侧盖成 $2$ 并获胜，所以甲会立刻取胜。

第二张是

甲三枚、乙两枚，轮到乙。乙把第一行右侧盖成 $2$，第一行凑满，乙胜。

样例2

输入

2
1 2 1 1 2 2 2 1 1
0 2 0 0 0 0 0 0 0

输出

0 -1

说明

第一张九格已满：

甲 $5$ 枚、乙 $4$ 枚，任何一行、一列、一条斜向都没有三枚相同的章，结果是平局。

第二张只有一枚乙的章，甲还一枚都没有。乙不能先盖，这张纸无效。