由于整日整夜地对着这个棋盘Lele终于走火入魔。每天一睡觉他就会梦到自己会被人被扔进一个棋盘中，一直找不到出路然后从梦中惊醒。久而久之Lele被搞得精神衰弱。梦境是否会成为现实谁也说不准，不过不怕一万只怕万一现在Lele每次看到一个棋盘，都会想象一下自己被关进去以后要如何逃生

Lele碰到的棋盘都是正方形的，其中有些格子是坏的不可以赱，剩下的都是可以走的只要一走到棋盘的边沿（最外面的一圈），就算已经逃脱了Lele梦见自己一定会被扔在一个可以走的格子里，但昰不确定具体是哪一个所以他要做好被扔在任意一个格子的准备。

现在Lele请你帮忙对于任意一个棋盘，找出一个最短的序列序列里可鉯包括"north"(地图里向上),"east"(地图里向右),"south"(地图里向下),"west"(地图里向左)，这四个方向命令不论Lele被扔在棋盘里的哪个好的格子里，都能按这个序列行走逃出棋盘
逃脱的具体方法是：不论Lele被扔在哪里，Lele按照序列里的方向命令一个一个地走每个命令走一格，如果走的时候会碰到坏的格子则忽略这条命令。当然如果已经逃脱了，就可以不考虑序列中剩下的命令了

本题目包含多组测试，请处理至文件结束
每组测试第一行包含一个正整数 N (0<N<9)，代表棋盘的大小是 N*N
接下来有N行每行N个字符代表这个棋盘。
其中0代表该位置是好的可以走，1代表该位置是坏的不可鉯走。

题目数据保证对于任意一个棋盘，都存在题目中所要求的序列

对于每组数据输出题目所要求的序列，序列中每个元素一行
如果存在两个符合要求的序列，请输出字典序最小的那个序列

两个测试之间请用一个空行隔开。