#941. 土拨鼠绕迷宫

土拨鼠绕迷宫

故事背景

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

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

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

题目描述

给定一个 nnn * 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(3t20)t(3 \le t \le 20), 表示共有多少组测试数据

第二行包含1个整数 n(3n8)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

提示

蛇形展开:

image