Escape from Tetris

Time Limit : 12000/4000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 1 Accepted Submission(s) : 1

Problem Description 由於整日整夜地對著這個棋盤，Lele終於走火入魔。每天一睡覺，他就會夢到自己會被人被扔進一個棋盤中，一直找不到出路，然後從夢中驚醒。久而久之，Lele被搞得精神衰弱。夢境是否會成為現實，誰也說不准，不過不怕一萬只怕萬一。現在Lele每次看到一個棋盤，都會想象一下自己被關進去以後要如何逃生。

Lele碰到的棋盤都是正方形的，其中有些格子是壞的，不可以走，剩下的都是可以走的。只要一走到棋盤的邊沿（最外面的一圈），就算已經逃脫了。Lele夢見自己一定會被扔在一個可以走的格子裡，但是不確定具體是哪一個，所以他要做好被扔在任意一個格子的准備。

現在Lele請你幫忙，對於任意一個棋盤，找出一個最短的序列，序列裡可以包括north(地圖裡向上),east(地圖裡向右),south(地圖裡向下),west(地圖裡向左)，這四個方向命令。不論Lele被扔在棋盤裡的哪個好的格子裡，都能按這個序列行走逃出棋盤。
逃脫的具體方法是：不論Lele被扔在哪裡，Lele按照序列裡的方向命令一個一個地走，每個命令走一格，如果走的時候會碰到壞的格子，則忽略這條命令。當然，如果已經逃脫了，就可以不考慮序列中剩下的命令了。

Input 本題目包含多組測試，請處理至文件結束。 每組測試第一行包含一個正整數 N (0