Division
Two mining companies found together a good spot for gold mining. Now, tough negotiations are coming: the plot of land needs to be split between the companies.
The terrain is square-shaped, and has been divided into n * n unit squares. Every small square is either empty, or contains one or two deposits of gold. Your goal is to split the plot into two connected parts, not necessarily identical or of the same area.
The simplest propositions are what the companies like best. Therefore, the border between their areas has to start in northwest corner, end in southeast corner, and must go along the unit squares' borders. Furthermore, the length of the border must not exceed 2n. Of course, the two parts must contain exactly the same number of gold deposits.
Input
The first line contains the number of test cases t. The test cases follow.
The first line of a test case contains a single integer n, the length of the side of the plot (1 ≤ n ≤ 1000). The next n lines contain the description of the plot: n rows containing n integers each. These are the numbers of gold deposits in the unit squares, equal to either 0, 1 or 2. The first row is the northernmost one, and every row is printed from its western end to the eastern one.
Output
For each test case, output:
either a single word IMPOSSIBLE, if there is no viable proposition of the land division,
or the description of the border, if a suitable proposition exists. Print a sequence of at most 2n letters N, E, S or W, describing the border from the northwest to the southeast corner. The letters mean that the border goes north, east, south or west, respectively.
If there are multiple solutions, output any one of them.