2048 is a famous single-player game in which the objective is to slide tiles on a grid to combine them and create a tile with the number 2048.
2048 is played on a simple 4 × 4 grid with tiles that slide smoothly when a player moves them. For each movement, the player can choose to move all tiles in 4 directions, left, right, up, and down, as far as possible at the same time. If two tiles of the same number collide while moving, they will merge into a tile with the total value of the two tiles that collided. *In one movement, one newly created tile can not be merged again and always is merged with the tile next to it along the moving direction first.* E.g. if the three "_2_" are in a row "_2 2 2_" and the player choose to move left, it will become "_4 2 0_", the two most left "_2_" are merged.
The above figure shows how 4 × 4 grid varies when player moves all tiles '_right_'.
Alice and Bob accidentally find this game and love the feel when two tiles are merged. After a few round, they start to be bored about the size of the board and decide to extend the size of board to n × n, which they called the game "_Super 2048_".
The big board then makes them dazzled. 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 (1 ≤ t ≤ 100). t test cases follow. The first line of each test case gives the side length of the board, n (1 ≤ n ≤ 20), 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). Each number in the grid is either 0 or a power of two between 2 and 1024, inclusive.
For each test case, n lines, each containing n space-separated integers which describe the board after the move in the same format as the input.
## Input
The first line of the input gives the number of test cases, t (1 ≤ t ≤ 100). t test cases follow. The first line of each test case gives the side length of the board, n (1 ≤ n ≤ 20), 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). Each number in the grid is either 0 or a power of two between 2 and 1024, inclusive.
## Output
For each test case, n lines, each containing n space-separated integers which describe the board after the move in the same format as the input.
[samples]
**Definitions**
Let $ t \in \mathbb{Z} $ be the number of test cases.
Let $ T = \{(n_k, \text{dir}_k, G_k) \mid k \in \{1, \dots, t\}\} $ be the set of test cases, where for each $ k $:
- $ n_k \in \mathbb{Z} $ denotes the side length of the square grid.
- $ \text{dir}_k \in \{\text{left}, \text{right}, \text{up}, \text{down}\} $ denotes the direction of movement.
- $ G_k = [g_{i,j}^{(k)}]_{n_k \times n_k} $ is an $ n_k \times n_k $ grid with $ g_{i,j}^{(k)} \in \{0\} \cup \{2^p \mid p \in \mathbb{Z}, 1 \leq p \leq 10\} $.
**Constraints**
1. $ 1 \leq t \leq 100 $
2. For each $ k \in \{1, \dots, t\} $:
- $ 1 \leq n_k \leq 20 $
- $ g_{i,j}^{(k)} \in \{0\} \cup \{2, 4, 8, \dots, 1024\} $ for all $ i,j \in \{1, \dots, n_k\} $
**Objective**
For each test case $ k $, compute the resulting grid $ G_k' = [g_{i,j}^{(k)'}]_{n_k \times n_k} $ after applying the following move operation in direction $ \text{dir}_k $:
- All non-zero tiles slide maximally in $ \text{dir}_k $ until blocked by the grid boundary or another tile.
- During sliding, if two adjacent tiles of equal value collide along the direction of motion, they merge into a single tile with value equal to their sum.
- Each tile can merge at most once per move, and merging occurs starting from the leading edge of the movement direction.
- Post-merge, no further merging is allowed in the same move.
- Empty spaces (zeros) are left behind after sliding.
Output $ G_k' $ for each $ k $.