Programming League 2004/05

A group of n children are playing with a set of n² flat square blocks. Each block is painted from above with one colour, and there are no more than 2 blocks of each colour. The blocks are initially arranged in an n x n square forming some sort of picture.

The children have been provided with some other n x n picture and asked to rearrange the blocks to that form. Since this is not really what they enjoy doing most, they intend to solve the task together and spend as little time on it as possible. Thus, every minute each child chooses a single 1 x n row or n x 1 column of blocks to rearrange. This row/column may never intersect with rows/columns chosen by other children in the same minute. A child takes one minute to perform any rearrangement (permutation) of the blocks within its row/column it likes.

Determine whether the children can perform their task of converting one block image into the other, and if so -- find the minimum possible time in minutes required to achieve this.

Input

The input starts with a line containing a single integer t<=200, the number of test cases. t test cases follow. Each test case begins with a line containing integer n (1<=n<=500). The next n lines contain n integers P_i,j each, forming a bitmap matrix representing the colours of the blocks in their initial configuration (1<=P_i,j<=n²). The following n lines contain n integers Q_i,j each, corresponding to the matrix for the final configuration (1<=Q_i,j<=n²).

Output

For each test case output a line with a single non-negative integer corresponding to the number of minutes required to transform matrix P into matrix Q, or the word no if no such transformation is possible.

Example

Input:
3
3
1 3 4
2 1 3
2 5 5
3 1 3
2 1 2
4 5 5
3
1 2 3
4 5 6
7 8 9
1 5 6
4 2 9
7 8 3
2
1 2
1 2
1 3
1 2

Output:
2
1
no

The actions taken in the first test case are illustrated below.