暂无测试数据。

蒜头君最近学习了矩阵乘法，所以他要多做练习

他的练习非常简单，拿到一个 $n * n$ 和矩阵 $A$ 和一个 $3 * 3$ 的矩阵 $B$，这里我们保证 $B$ 矩阵中所有数字的和为 $1$

为了方便输入 $B$ 矩阵,我们定义一个新的 $C$ 矩阵，设 $C$ 矩阵中的所有数字和为 $sum$ ，那么 $B_{i,j} = C_{i,j} / sum$

接着我们再定义一个运算 $G=g(A,B)$ 表示对 $A,B$ 矩阵的每个元素进行以下运算得到矩阵 $G$

$G_{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}* B_{i,j})$

再定义 $g^m(A,B) = g(g^{m-1}(A,B),B)$ 且 $g^1(A,B) = g(A,B)$

现在蒜头君想知道 $\lim_{t\to \infty}g^t(A,B)$ 的结果是什么

输入格式

输入第一行包含两个正整数 $T$，表示总共有 $T$ 组测试数据

对于每组测试数据：第一行包含一个正整数 $n$ 表示 $A$ 矩阵大小接下来 $n$ 行每行 $n$ 个整数表示一个 $n * n$ 的 $A$ 矩阵接下来 $3$ 行每行 $3$ 个整数表示一个 $3 * 3$ 的 $C$ 矩阵

输出格式

对于每组数据输出最终的矩阵 $G,G = \lim_{t\to \infty}g^t(A,B)$

数据范围

对于 $30\%$ 的数据，$T=1, 3 \leq n \leq 5, 0 \leq A_{i,j},C_{i,j} \leq 10$

对于 $100\%$ 的数据，$1\leq T \leq 100, 3 \leq n \leq 50, 0 \leq A_{i,j},C_{i,j} \leq 1000$

题目保证 $C$ 矩阵不会全为 $0$

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

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