3x3 Convolution

Given an $n\times n$ matrix $A$ and a $3\times 3$ matrix $K$. These two matrices are very special : they are both non-negative matrices and the sum of all elements in matrix $K$ is 1 (In order to avoid floating-point error, we will give matrix $K$ in a special way in input).

Now we define a function $C(A,K)$, the value of $C(A,K)$ is also a $n\times n$ matrix and it is calculated below(we use $C$ to abbreviate $C(A,K)$):

$C_{x,y}=\sum_{i=1}^{min(n-x+1,3)}\sum_{j=1}^{min(n-y+1,3)}A_{x+i-1,y+j-1}K_{i,j}$

Now we define $C^{m}(A,K)=C(C^{m-1}(A,K),K)$ and $C^{1}(A,K)=C(A,K)$, Kanade wants to know $lim_{t\rightarrow \infty}C^{t}(A,K)$

It's guaranteed that the answer exists and is an integer matrix.

There are $T$ test cases in this problem.

The first line has one integer $T$.

Then for every test case:

The first line has one integer $n$.

Then there are $n$ lines and each line has $n$ non negative integers. The j-th integer of the i-th row denotes $A_{i,j}$

Then there are $3$ lines and each line has $3$ non negative integers. The j-th integer of the i-th row denotes $K'_{i,j}$

Then $K$ could be derived from $K'$ by the following formula: $$K_{i,j}=K'_{i,j}/(\sum_{x=1}^{3}\sum_{y=1}^{3}K'_{x,y})$$

$1\leq T\leq 100$

$3\leq n\leq 50$

$0\leq A_{i,j}\leq 1000$

$0\leq K'_{i,j}\leq 1000$

$\sum_{x=1}^{3}\sum_{y=1}^{3}K'_{x,y}>0$

For each test case, output the answer matrix by using the same format as the matrix $A$ in input.

2
3
1 2 3
4 5 6
7 8 9
3 0 0
0 0 0
0 0 0
3
1 2 3
4 5 6
7 8 9
1 0 0
0 1 0
0 0 0

1 2 3
4 5 6
7 8 9
0 0 0
0 0 0
0 0 0

2020中国大学生程序设计竞赛（CCPC） - 网络选拔赛