问题描述

在跟张老师一起训练的过程中，张老师的队友们发现张老师的算术能力特别差，已经基本影响到了最基本的复杂度计算了。所以张老师的队友们决定给张老师出一些题目来锻炼张老师的算术能力。张老师的队友们也没有太多的时间，因此张老师的队友们决定出一些计算量比数据规模大很多的题。

张老师的队友们给出了 $n$ 个矩阵 $\{A_i\}$，第 $i$ 个矩阵的大小为 $2^{n-i+1} \times 2^{n-i}$，要求很简单，计算 $\prod_{i=1}^n A_i$ 的结果。

由于张老师着急去陪新格尔公司的天才程序员菜哭武、牛乐武、菜喜武玩方格游戏，因此张老师没有时间去进行如此大量的计算，所以他希望智慧的你可以写个程序来帮助他完成这件事情。

最后的结果对 $977317$ 取模。矩阵中的每个元素不超过 $9060$。

输入格式

输入包含多组数据。

第一行，一个正整数 $T$，表示数据组数。

对于每组数据的第一行，只有一个整数 $n$，表示一共有 $n$ 个矩阵。

接下来输入分成 $n$ 个部分，每个部分包含问题描述中所描述的矩阵。

题目保证 $n \leq 10$。

输出格式

每组数据第一行输出 Case #i:。其中 $i$ 表示该组数据的编号，从 $1$ 开始计数。

接下来输出 $\prod_{i=1}^n A_i$ 的结果，矩阵中的每行元素单独占据一行，相同行中的元素使用空格隔开。

样例输入

2
1
2
1
2
0 0
0 0
0 0
0 0
1
1

样例输出

Case #1:
2
1
Case #2:
0
0
0
0

提示

Tips：矩阵乘法最低复杂度为 $O(n^{2.3728639})$，详情请阅读：

https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm