The big board then makes them dazzled (no zuo no die -_-| ). They ask you to write a program to help them figure out what the board will be looked like after all tiles move to one specific direction on a given board.
The first line of the input gives the number of test cases, T. T test cases follow. The first line of each test case gives the side length of the board, N, and the direction the tiles will move to, DIR. N and DIR are separated by a single space. DIR will be one of four strings: "left", "right", "up", or "down".
The next N lines each contain N space-separated integers describing the original state of the board. Each line represents a row of the board (from top to bottom); each integer represents the value of a tile (or 0 if there is no number at that position).
For each test case, output one line containing "Case #x:", where x is the test case number (starting from 1). Then output N more lines, each containing N space-separated integers which describe the board after the move in the same format as the input.
Each number in the grid is either 0 or a power of two between 2 and 1024, inclusive.
1 ≤ T ≤ 20
1 ≤ N ≤ 4
1 ≤ T ≤ 100
1 ≤ N ≤ 20