Let's call a grid 8-puzzle board if the gridsize is 3 x 3 and there is exactly one cell is 'x' and others are '1' or '0'.
In one operation, you can exchange the 'x' cell of a 8-puzzle board with any cell which is adjacent to the 'x' cell. The cell (i, j) is adjacent to the cell (i-1, j), (i, j-1), (i, j+1) and (i+1, j).
Now you need to solve T tasks. In each task, you are given two 8-puzzle boards A, B and one integer K. You need to answer whether it's possible to make A into B in at most K operations.
Let's take an example. In the first task of Sample, you can make A into B in the following 2 operations:
0 x 0 0 0 x 0 0 1
1 0 1 ========> 1 0 1 ========> 1 0 x
0 1 1 0 1 1 0 1 1
exchange (1,3) exchange (2,3)
The first line contains an integer T (1 ≤ T ≤ 10) – the number of tasks you need to solve.
And for each task, first you are given one integer K (0 ≤ K ≤ 9) – the maximum number of operations you can execute. Then you are given A and B. Both of them are in 3 lines of 3 characters. Please refer to Sample Input.
For each task output "Yes" if it's possible to make A into B in K operations. Otherwise output "No". Then print a newline('\n').