【问题描述】

古时候有一高人发明了一种二人对弈的游戏―控制棋。游戏规则如下:在一个棋盘上有N点,两点之间如画有一条线则表示两点相连,两点之间只有一条边,且一个点不能与自己相连。两人轮流把起棋子放在点上,如果一点被放上棋子,则这一点和与之相连的点就都被控制了。不能把棋子放在被控制的点上。初始时,棋盘上的点都没有被控制。当轮到某一方下而无法落子时,另一方得胜。
  由于控制棋变化多端,从发明到现在没有一个人可以根据棋盘的初始状态来判定先手是否必胜。请你编程来解决这个千古难题。

 

【输入】

  输入第一行为一个整数K1<=K<=25,表示文件包含K个版块。每个版块由若干行组成,版块间有一空行隔开,每个版块描述一个棋盘,棋盘用一个邻接矩阵A表示。A[ij]=1表示点i和点j间有边相连,如果A[ij]=0则示不相连。每个版块的第一行包括整数(1<=N<=30)N是棋盘的顶点数。以下N行为一个棋盘。

【输出】

  包含K行,每行为个数。若对于第i棋盘,先手必胜,则输出'1',否则输出'0'


【样例输入】

3
4
0 1 0 0
1 0 1 1
0 1 0 0
0 1 0 0


4
0 1 0 1
1 0 1 1
0 1 0 0
1 1 0 0


2
0 0
0 0

【样例输出】

1
1
0