题目内容

在一个 $3 \times 3$ 的棋盘上，两位玩家依次下子，先手执 “$X$” 棋子，后手执 “$O$” 棋子。棋盘格子用行坐标 $x$ 和列坐标 $y$ 表示，均从 $1$ 开始编号。给出完整的落子过程，判断这一盘棋的最终结果：

• 若存在不合法操作（包括在一方胜利后仍继续落子，或下在已有棋子的位置），输出 $-1$。
• 若先手获胜（形成三子连线），输出 $0$。
• 若后手获胜，输出 $1$。
• 若处理完所有落子后无人获胜且不存在不合法操作，输出 $2$。

输入描述

第一行输入一个整数 $T$（$1 \le T \le 2 \times 10^4$），表示测试数据的组数。

此后对于每组测试数据：

第一行输入整数 $n$（$3 \le n \le 9$），表示总落子次数；

接下来 $n$ 行，每行输入两个整数 $x, y$（$1 \le x, y \le 3$），表示第 $i$ 次落子的位置；

当 $i$ 为奇数时为先手下“$X$”，偶数时为后手下“$O$”。

输出描述

对于每组测试数据，输出一行结果：

若存在不合法操作，输出 $-1$；

若先手获胜，输出 $0$；若后手获胜，输出 $1$；

若无人获胜，输出 $2$。

样例1

输入

4
5
1 1
2 1
1 2
2 2
1 3
6
1 1
2 1
1 3
2 2
3 1
2 3
3
1 1
1 1
2 2
9
1 1
1 2
1 3
2 3
2 1
2 2
3 2
3 1
3 3

输出

0
1
-1
2

说明

第一组：先手在第 $1,3,5$ 步分别落子 $(1,1),(1,2),(1,3)$，第一行三子连线获胜，输出 $0$。

第二组：后手在第 $2,4,6$ 步分别落子 $(2,1),(2,2),(2,3)$，第二行三子连线获胜，输出 $1$。

第三组：第二步在已有棋子的位置 $(1,1)$ 落子，操作不合法，输出 $-1$。

第四组：九步全部落子完毕，无人形成三子连线，输出 $2$。