Problem Description

A magic square is a $3 \times 3$ square, where each element is a single digit between 1 and 9 inclusive, and each digit appears exactly once. There are 4 different contiguous $2 \times 2$ subsquares in a magic squares, which are labeled from 1 to 4 as the following figure shows. These $2 \times 2$ subsquares can be rotated. We use the label of the subsquare with an uppercase letter to represent a rotation. If we rotate the subsquare clockwise, the letter is 'C'; if we rotate it counterclockwise, the letter is 'R'. The following figure shows two different rotations.

Now, given the initial state of a magic square and a sequence of rotations, please print the final state of the magic square after these rotations are performed.

Input

The first line of input is a single integer $T$ $(1 \leq T \leq 100)$, the number of test cases.

Each test case begins with a single integer $n$ $(1 \leq n \leq 100)$, the number of rotations. It is then followed by a $3 \times 3$ square, where every digit between 1 and 9 inclusive appears exactly once, representing the initial state of the magic square. The following $n$ lines describe the sequence of rotations.

The test data guarantees that the input is valid.

Output

For each test case, display a $3 \times 3$ square, denoting the final state of the magic square.

1
2
123
456
789
1C
4R

413
569
728