一个 $n \times m$ 个节点的图 $G$ 构成了一个 $n \times m$ 的网格。有 $(n-1) \times m$ 条带权边连接相邻行的顶点，有 $n \times (m-1)$ 条带权边连接相邻列的顶点。

图 $G$ 的生成树是一个包含所有顶点且为树的子图。最小生成树（MST）是指权重小于或等于所有其他生成树权重的生成树。图 $G$ 有许多不同的最小生成树。对于每棵 MST $T$，节点 $u$ 的 $LRdeg(u)$ 定义为：与 $u$ 相连的位于前一列或前一行的节点数量加 1。我们定义 $\tau(T) = \prod_{u} LRdeg(u)$ 为所有节点 $LRdeg(u)$ 的乘积。

你的任务是求出图 $G$ 的最小生成树的权重，并计算所有最小生成树的 $\tau(T)$ 之和。如果两棵 MST 包含的边集不同，则认为它们是不同的。

输入格式

输入包含多个测试用例。输入的第一行是一个整数 $t$ ($1 \le t \le 32$)，表示测试用例的数量。接下来是 $t$ 个测试用例。

对于每个测试用例，第一行包含两个整数 $n$ ($1 \le n \le 800$) 和 $m$ ($1 \le m \le 7$)。接下来的 $n$ 行，每行包含 $m-1$ 个整数，描述连接相邻列顶点的边的权重。再接下来的 $n-1$ 行，每行包含 $m$ 个整数，描述连接相邻行顶点的边的权重。 边的权重不超过 10。

输出格式

对于每个测试用例，输出一行，包含两个整数。第一个整数是最小生成树的权重。第二个整数是所有不同最小生成树的 $\tau(T)$ 之和，对 $10^9 + 7$ 取模。

样例

样例输入 1

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

样例输出 1

Case #1: 37 288
Case #2: 96 4478976