Super 2048 (Large)

2048 is a single player game played on a 4 x 4 grid. On each move every tile slides as far as it can in one of four directions: left, right, up, or down. If two tiles holding the same number collide while sliding, they merge into one tile holding the sum of the two numbers.

Two rules settle what happens when three or more equal tiles line up. A tile created by a merge cannot merge again during the same move, and a tile merges first with the neighbour nearest to it along the moving direction. For example, a row 2 2 2 moved left becomes 4 2 0. The two leftmost tiles merge, and the new 4 stays as it is.

The figure shows how a 4 x 4 grid changes when every tile moves right.

Alice and Bob got bored with the 4 x 4 board and widened it to N x N, a game they call Super 2048. The larger board is hard to follow by eye. Given one board and one direction, compute the board after every tile moves in that direction.

The first line has the number of test cases $T$. The first line of each test case has the side length of the board $N$ and the direction $DIR$ the tiles move to, separated by one space. $DIR$ is one of left, right, up, down.

The next $N$ lines each have $N$ integers separated by spaces, describing the starting board. Each line is one row of the board, from the top row to the bottom row, and each integer is the value of the tile in that cell. An empty cell is 0.

Limits

• $1 \le T \le 100$
• $1 \le N \le 20$
• Every number on the board is 0 or a power of two between 2 and 1024.

For each test case, print one line Case #x:, where $x$ is the test case number starting from 1. Then print $N$ lines describing the board after the move, in the same format as the input, with $N$ space separated integers per line.