题意简述
有RxC个房间，每个房间里都有一个人。

房间有东南西北四扇门，只有一个门可以从里面打开，每个人也只能走自己打开的门，可以在这些房间内自由行走。

如果门通向该矩阵外部，通过这扇门后，这个人就成功逃脱。

问如果想让K个人逃脱，每个房间里可打开的那扇门应设置在哪个方向。

若无法造成K个人逃脱的局面，输出IMPOSSIBLE

Problem
You are designing a new “escape” adventure that uses a rectangular grid of rooms (unit cells) with R rows and C columns. Each room has four doors oriented in the four orthogonal directions of the grid: north, south, east, and west. The doors on the border of the grid lead outside, and all of the other doors lead to other rooms.

The adventure will be played by exactly R × C players, with each player starting in a different one of the R × C rooms. Once everyone is in position and the game starts, all of the doors close, and there is a mechanical trick: one of the four doors in each room can be opened from inside the room, and the other three doors cannot be opened. This remains consistent throughout the adventure; in a given room, it is always the same door that can be opened. Notice that it is possible that a door that connects two rooms might be able to be opened from one side but not the other.

Each player moves independently of all other players. Players can only go through doors that they opened themselves, and they must close doors behind them. Each player will keep going through doors until they go through a door that leads outside (and therefore they escape), or they have made R × C moves without escaping (at which point they are considered to have failed, and they do not escape).

You want to choose which door in each room can be opened, such that exactly K of the players will be able to escape. Can you find a way to do this, or determine that it is IMPOSSIBLE?

Input
The first line of the input gives the number of test cases, T. T test cases follow. Each consists of one line containing three integers R, C, and K, as described above.

Output
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is IMPOSSIBLE if there is no solution, or POSSIBLE if there is. If there is a solution, output R more lines of C characters each, representing the grid of rooms. The j-th character on the i-th of these lines represents the room in the i-th row and j-th column of the grid; each character must be either uppercase N, S, E, or W, according to whether the door that opens from that room is the one that leads north, south, east, or west.

If multiple answers are possible, you may output any one of them.

Limits
1 ≤ T ≤ 100.
Time limit: 20 seconds per test set. (10 seconds per test run.)
Memory limit: 1GB.
1 ≤ R.
1 ≤ C.
0 ≤ K ≤ R × C.

Test set 1 (Visible)
1 ≤ (R × C) ≤ 8.

Test set 2 (Hidden)
1 ≤ (R × C) ≤ 100.

Sample

Input

2
2 3 2
1 1 0

Output
Case #1: POSSIBLE
SES
SNW
Case #2: IMPOSSIBLE

In our solution for Sample Case #1, the two players who start in the westernmost two rooms will go south until they escape, whereas the four players who start in the other four rooms will travel between those rooms in an endless clockwise circle and cannot escape.

In Sample Case #2, there is only one room, so the player can definitely escape regardless of which particular door can be opened.

/*
  稍加思考就能发现，除了只有一格房间的情况下，其他的房间数都可以互相连通封闭在一起，
  通过自闭达到出不去的自闭状态。

  若除了某房间外，剩下房间的人都可走向门外，
  则某房间的人既不能通向别的房间也不能直接通向门外，无路可走不符合题意。

  所以仅K=RxC-1的情况为impossible。

  然后接下来用最方便的方法构建自闭房间即可，答案不唯一。
*/
#include <bits/stdc++.h>
using namespace std;

int main(){

    int T;
    cin >> T;
    for (int t=0; t<T; t++){

    int r, c, k;
    cin >> r >> c >> k;
    if (k==r*c-1){
        cout << "Case #" << t+1 << ": ";
        cout << "IMPOSSIBLE\n";
    }else{
        cout << "Case #" << t+1 << ": POSSIBLE\n";
        k=r*c-k;//有k个人不能走
        int anz=0;
        if (c==1){//c==1的特判

            //不能走的人里一个人往南走，另外k-1个人往北走，形成死路。
            cout << "S\n";
            for (int i=1; i<k; i++){
                cout << "N\n";
            }
            //剩下的人往南走
            int e=1;
            for (int i=max(k, e); i<r*c; i++){
                cout << "S\n";
            }
            continue;
        }

        for (int i=0; i<r; i++){
            for (int j=0; j<c; j++){
                if (i==0 && j==0){
                    cout << "E";//第一格固定往东走
                    anz++;
                }else{
                    if (i==0){
                        if (anz<k){
                            cout << "W";//第一行在有人没走的时候往西走，否则往东走
                            anz++;
                        }else{
                            cout << "E";
                        }
                    }else{
                        if(anz<k){
                            cout << "N"; //其他行在有人没走的时候往北走，否则往南走
                            anz++;
                        }else{
                            cout << "S";
                        }
                    }
                }
            }
            cout << "\n";
        }

    }
    }

}