1050. 方阵相乘

Naive循环多维数组基本算法

时间限制:2000 ms

内存限制:256 MiB

题面

实现两个 n×nn \times n 方阵相乘的 Strassen 算法,这里假设 nn 为 2 的方幂。

输入格式

第一行为一个正整数 NN, 表示有几组测试数据。

每组测试数据的第一行为一个正整数 nn (1n1001 \le n \le 100),nn 为 2 的方幂,表示方阵 n×nn \times n

接下去的 nn 行表示第一个方阵,每行有 nn 个整数,用空格分开。

再接下去的 nn 行表示第二个方阵,每行有 nn 个整数,用空格分开。

输出格式

对于每组测试出据,输出 nn 行,每行有 nn 个整数,用空格分开,不能有多余的空格。

样例

输入

1
2
1 2
3 4
5 6
7 8

输出

19 22
43 50