You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

故事背景

土拨鼠稀里糊涂地走进了一个 $n * n$ 的且仅由0和1组成的矩阵迷宫的左上角，这时，土拨鼠身后的门突然封闭起来了。

这时，一艘外星飞船从天而降，对土拨鼠说：“现在你已经到了矩阵迷宫的左上角，你需要在这个矩阵中蛇形的绕圈寻找所有的1。最后以你走过的路径展开，得到一个由01组成的二进制序列。接下来你需要将这个二进制序列转为十进制。如果这个十进制数能被你刚所找到的1的个数整除，则你可以离开迷宫。否则就永远别想出去了。”

现在外星飞船从迷宫上空拍下迷宫的全貌并发给你，请你编程计算一下土拨鼠能否顺利逃出。

题目描述

给定一个 $n * n$ 的正方形01矩阵，请你按照蛇形将矩阵变为一个二进制数并转为十进制。同时你还要找到矩阵中1的个数。如果十进制数能整除1的个数，则输出y，否则输出n.

将以下矩阵展开

0 1 0 1
1 0 1 1
0 0 1 0
1 0 0 1

得到二进制数0101110100101001

转为十进制是23849

矩阵中有8个1

23849不能整除8

所以这个矩阵土拨鼠不能逃出

输入格式

第一行包含一个整数 $t(3 \le t \le 20)$, 表示共有多少组测试数据

第二行包含1个整数 $n(3\leq n\leq 8)$，表示矩阵的高和宽。

接下来输入一个矩阵（带空格），且矩阵中只有0和1。

输出格式

输出t行数据, 判断土拨鼠能否顺利逃出这个矩阵。能则输出y，不能则输出n。

样例

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

n

23849 % 8 = 1

2
2
1 1
0 0
4
0 1 0 1
1 0 1 1
0 0 1 0
1 0 0 1

y
n

12 % 2 = 0

23849 % 8 = 1

提示

蛇形展开：