Problem Description

Hamilton is a Canadian city near Toronto, and a nice place to take a walking tour.

In this problem, Hamilton is represented by a grid of unit cells with $2R$ rows and $2C$ columns, where each cell is either empty (represented by *) or contains a building (represented by #). The cell on the $i$-th row and $j$-th column is represented by $A_{i,j}$ where $1 \le i \le 2R$ and $1 \le j \le 2C$. It is not possible to enter cells containing buildings and you can only move to an adjacent cell that shares a side with the current cell (not just a corner). The grid is such that if it is divided evenly into $2 \times 2$ blocks of unit cells, then in each of those blocks, either all four cells are empty, or all four cells are occupied by a building. Let us represent the block formed by $A_{2i-1,2j-1}$, $A_{2i-1,2j}$, $A_{2i,2j-1}$, and $A_{2i,2j}$ cells as $B_{i,j}$ where $1 \le i \le R$ and $1 \le j \le C$.

Grace is a tourist in Hamilton and wants to visit all the empty cells in Hamilton. Grace is currently in cell $A_{1,1}$. Visiting the same cell twice could be boring for her. Hence, Grace wants to visit each of the empty cells exactly once and finally end in cell $A_{1,1}$. Can you help Grace by providing a string (consisting of directional moves $\{N, E, S, W\}$ representing the unit moves to the north, east, south, or west respectively) which Grace can follow to visit every empty cell once and end again in $A_{1,1}$.

Input Format

The first line of the input gives the number of test cases, $T$. $T$ test cases follow.

The first line of each test case contains $2$ integers $R$ and $C$.

The next $R$ lines of each test case contains $C$ characters each.

The $j$-th character on the $i$-th of these lines represents the block $B_{i,j}$ formed by the following $4$ cells: $A_{2i-1,2j-1}$, $A_{2i-1,2j}$, $A_{2i,2j-1}$, and $A_{2i,2j}$.

If $B_{i,j} = \#$, all $4$ of the cells in $B_{i,j}$ are occupied by a building.

Otherwise, if $B_{i,j} = \ast$, all $4$ of the cells in $B_{i,j}$ are empty.

Output Format

For each test case, output one line containing Case #$x$: $y$, where $x$ is the test case number (starting from $1$) and $y$ is the answer to the problem as follows.

If there is no solution to the problem, $y$ should be IMPOSSIBLE. Otherwise, $y$ should be a sequence of characters from the set $\{N, E, S, W\}$, representing the unit moves (to the north, east, south, or west respectively) in a valid route, starting from $A_{1,1}$, as described in the statement above.

Note that your last move should take you to $A_{1,1}$; this move does not count as visiting the same cell twice.

If there are multiple valid solutions, you may output any one of them.

3
1 1
*
2 2
**
*#
3 4
****
*#*#
****

Case #1: SENW
Case #2: SSSENNEENWWW
Case #3: ESSSSEEENNNWWNEEEEESWWSSSEESWWWW

3
3 1
*
*
#
1 3
*#*
3 4
**#*
**#*
****

Case #1: SSSENNNW
Case #2: IMPOSSIBLE
Case #3: ESSSSENNNNESSSSEEENNNNESSSSSWWWW

Hint

The sample output displays one set of answers to the sample cases. Other answers may be possible.

In Sample Case #$1$, Grace will follow the route $A_{1,1}$, $A_{2,1}$, $A_{2,2}$, $A_{1,2}$, and finally $A_{1,1}$. Note that ESWN is the only other possible valid answer.

The image below shows one of the possible routes for Sample Case #$1$.

:::align{center} :::

The image below shows one of the possible routes for Sample Case #2.

:::align{center} :::

Limits

$1 \le T \le 100$.

$1 \le R \le 200$.

$1 \le C \le 200$.

All characters in the grid are from the set $\{\#, \ast\}$.

The first character of the first line of the input grid for each test case is a * character, i.e. $B_{1,1} = \ast$.

Test Set $1$

A block contains buildings if and only if the row number and column number of it are divisible by $2$. i.e. $B_{i,j} = \# \iff ((i \bmod 2 = 0) \land (j \bmod 2 = 0))$.

Test Set $2$

No extra constraints.