Square Grid Puzzle

In this puzzle, you get a $0$-indexed $N \times N$ square grid of distinct integers from $0$ to $N \times N - 1$, inclusive. The goal is to reach the ordered state where the number in row $i$ and column $j$ equals $i \times N + j$ for every $0 \le i, j < N$. You can reach this goal with two types of moves:

• D move (down): written as "D $a[0]$ $a[1]$ $\dots$ $a[N - 1]$", where $a[0], a[1], \dots, a[N - 1]$ is a rearrangement of the numbers in the top row. The move removes the top row and adds a new row at the bottom of the grid. The new row holds $a[0]$ through $a[N - 1]$ from left to right.
• R move (right): written as "R $b[0]$ $b[1]$ $\dots$ $b[N - 1]$", where $b[0], b[1], \dots, b[N - 1]$ is a rearrangement of the numbers in the leftmost column. The move removes the leftmost column and adds a new column at the right of the grid. The new column holds $b[0]$ through $b[N - 1]$ from top to bottom.

A rearrangement changes only the order of the numbers, without adding or removing any of them. It may also keep the original order.

For example, suppose the current grid is:

The move "D $6$ $2$ $4$" produces:

The move "R $2$ $8$ $7$" instead gives:

For $N = 3$, the target grid is:

You aim to solve the puzzle with fewer than $3 \times N$ moves. You can still earn partial points with more moves or without solving the puzzle.

The first line contains a single integer $N$. The following $N$ lines describe the initial grid, with $N$ numbers on each line.

The first line contains a single integer $M$, the number of moves. Each of the following $M$ lines contains one move.

$2 \le N \le 9$. Each value of $N$ from $2$ to $9$ has the same number of test cases.