Flying Piglets

"Oh my god, how are our pigs flying!" Jiajia stood there, stunned, watching the piglets floating above her house. "How can I get them back into their respective pens?"

"Jiajia, wake up!" Hearing her mother's voice, Jiajia's eyes lit up, and she sat up in bed. "So it was just a dream. How amazing..." While eating breakfast, Jiajia was still reminiscing. "Wouldn't it be interesting if what happened in the dream actually came true?" Unable to finish her breakfast, Jiajia immediately found a piece of paper and started drawing on the table.

Jiajia drew an $n \times n$ grid map, representing the space above the pig pens divided into $n$ rows and $n$ columns, numbered $0, 1, 2, \dots, n-1$ from top to bottom and $0, 1, 2, \dots, n-1$ from left to right. A cell at row $x$ and column $y$ is denoted as $(x, y)$. She drew an asterisk "*" in $m$ of these cells, representing the pig pens, and placed a pig with a specific movement direction in each of the other $m$ cells. We label these pigs $0, 1, 2, \dots, m-1$ from top to bottom and left to right. In other words, if two pigs have initial positions $(x_1, y_1)$ and $(x_2, y_2)$ with labels $l_1$ and $l_2$ respectively, then $l_1 < l_2$ if and only if: (1) $x_1 < x_2$; or (2) $x_1 = x_2$ and $y_1 < y_2$. Jiajia defined the movement directions numerically: $5$ means stationary, $2$ means south, $4$ means west, $6$ means east, and $8$ means north. Every second, each pig moves one cell in its current direction, unless it has already entered a pig pen. If a pig at the boundary moves one cell outward, it is considered to have returned to the opposite boundary. For example, a pig moving east at the right boundary will enter the left boundary cell after one second. For clarity, the position of a pig at $(x, y)$ in the next second is shown in the table below.

Table 1. Direction and Next Position

Jiajia hopes to control the movement of the piglets, so she designed five "blowing" operations. Each operation is performed once per time unit and can change the movement direction of all pigs in a specific row or column. The five operations are as follows:

Please note that the last four operations only change the movement direction and do not affect the pigs' positions.

The movement of the pigs is measured in seconds, starting at time $0$. At the beginning of each second, Jiajia performs a blowing operation, changing the direction of some (possibly zero) pigs, and then all pigs move according to Table 1. If multiple pigs move into a certain pig pen at the next moment, the one with the smallest label enters the pen. Other pigs can still enter that cell, but it is not considered entering a pen. In other words, the pig with the smallest label and the pen disappear simultaneously. This is because one pen can only hold one pig; once a pig has fallen into it, we can consider that pen and that pig to have disappeared.

Let $t_i$ be the time when pig $i$ enters a pen ($i=1, 2, \dots, n$), $T_1 = \max\{t_i\}$, and $T_2 = \sum t_i$. Jiajia's goal is to make $T_2$ as small as possible. Jiajia knows this task is very difficult, so she will reward you based on the relative quality of your $T_2$ compared to the currently known best $T_2$.

Input

The input files airpig1.in to airpig10.in are provided. The first line of each file contains the test case number caseN. The second line contains a single integer $n$, the size of the map. The following $n$ lines, each containing $n$ characters, describe the map. The character "." represents an empty space, "*" represents a pig pen, and the characters 5, 2, 4, 6, 8 represent the movement directions of the pigs in the sky (5 is stationary, 2 is south, 4 is west, 6 is east, 8 is north).

Output

This is an answer-submission problem. You should provide ten output files airpig1.out to airpig10.out. The first line of each file must be the test case number caseN, which should match the corresponding input file. The second line contains two integers $T_1$ and $T_2$, where $T_1$ is the time the last pig enters a pen, and $T_2$ is the sum of the times all pigs enter their pens. The following $T_1$ lines each contain a string representing the blowing operation performed at each time step. See Table 2 for the output format of the blowing operations.

Examples

Input 1

1
5
...*.
..5..
..5..
*....
.....

Output 1

1
4 7
E2
E1
N3
S0

Note

Subtasks

For each test case, if your output is incorrect, you receive 0 points. Otherwise, your score is calculated as follows: $score = \lfloor \text{currently known best output} / \text{your output} \times 9 \rfloor + 1$. Where $\lfloor x \rfloor$ denotes the largest integer not exceeding $x$.

Implementation Details

A test program check is provided. Usage: check <test case number X>. The program will automatically read the input file airpigX.in and your output file airpigX.out, where $X=1, 2, \dots, 10$. The program will display whether your result is correct on the screen.