Consider a n×n size board (1≤n≤10), wherein every cell has a number written on it. The rows and columns are cyclic. So you can slide any row/column any number of blocks or any number of times. As an example in the board given below, we slide the middle row one block each repeatedly, and the results are given in the following figures.

A unit move in this game is sliding any 1 row (or 1 one column) any number of times. So the motions made above is one single move of the game. Given a source configuration and a goal configuration, print the moves that result in the goal configuration from a source configuration using Iterative Deepening. Moving rows is preferred to moving columns (primary criterion), an earlier row/column is preferred to a later one (secondary criterion), sliding lesser rightward/downward is preferred to sliding more (tertiary criterion).

The first line of input is the number of test cases. For every test case, the first line of input is n, the size of the game. The next n lines with n integers each is the source configuration. The next n lines with n integers each is the goal configuration.

The output is variable number of lines, each line indicating the board configuration of a move printed in a row major format.