L. 五子棋

众所周知，五子棋是一个简单的游戏，一旦一方的五个的棋子连成一条连续的线，那么这一方就赢了。

L很喜欢这个游戏，但他不想看到自己的失败，所以他会在要输的时候选择秒退。但有时候L并不能意识到自己的失败，所以他希望你能帮助他进行判断：如果轮到他落子时，无论落到哪里，他都赢不了，并且对手能在下一步获得胜利时，他希望可以自动退出游戏。这样一来他就不会看到自己失败，这样他的心情就会一直很好。

所以L现在需要你帮忙完成这个判断。

L先落子

第一行包含一个整数 $t$（$1\leq t \leq 100$），代表数据组数。

每组数据第一行包含一个整数 $n$（$1\leq n \leq 15$），代表棋盘大小。

接下来$n$行，每行一个长度为$n$的字符串，代表棋盘每行的情况，$0$代表空,$1$代表L的落子，$2$代表对手的落子。

输入不保证$1$和$2$的数量相等，但保证不存在已经五子连珠的情况，也不会出现少于两个空格的情况。

共$t$行，每行一个整数，$1$代表无论L需要退出游戏，$0$代表不需要退出游戏。

样例输入

2
7
0100000
0012000
0021000
0200200
0222200
0010100
0011100
7
0000000
0020000
0002000
1111200
0002000
0020000
0000000

样例输出

1
0

样例解释

第一张图出现4个连续的2,且两边没有阻拦，不论L怎么下，对手下一步都能赢，所以要退出游戏。

第二张图，虽然对手一定能赢，但无法在下一步获胜，即L无法判断是否一定会输，所以无需退出游戏。