在道路交叉口，通常会有交通信号灯来指示行人何时可以过马路。聪明的行人可能会根据信号灯变绿的时间来优化她在城市中的路径。

本题中的城市是一个 $N$ 行 $M$ 列的网格。行人希望从西南街区的东北角走到东北街区的西南角。你的目标是帮助她找到从起点到终点的最快路径。

行人穿过一条街道需要 1 分钟，但前提是交通信号灯在整个穿越过程中必须保持绿色。行人可以在两个街道之间沿街区的一条边移动，耗时 2 分钟。行人只能沿着街区的边移动；她不能从一个街区的角落对角线移动到对角。

交通信号灯遵循以下规律：在交叉口 $i$，南北向信号灯保持绿色 $S_i$ 分钟，此时东西向信号灯为红色。随后南北向信号灯变红，东西向信号灯变绿，并保持 $W_i$ 分钟。之后循环往复。行人从 $t=0$ 分钟开始移动；交通信号灯 $i$ 在 $t=T_i$ 分钟时开始南北向绿灯的循环。在 $t=T_i$ 之前也存在同样的循环。

例如，交叉口 0 可能具有以下值：

S_0 = 3, W_0 = 2, T_0 = 0

南北方向在 0 分钟后变绿。绿灯持续 3 分钟，在此期间行人可以穿过南北方向，但不能穿过东西方向。随后信号灯切换，在接下来的 2 分钟内，行人可以穿过东西方向，但不能穿过南北方向。之后，在开始 5 分钟后，循环再次开始。这与以下配置完全相同：

S_0 = 3, W_0 = 2, T_0 = 10

输入格式

输入的第一行包含测试用例的数量 $C$。接下来是 $C$ 个测试用例，格式如下： 一行包含 "$N$ $M$"，其中 $N$ 和 $M$ 分别是水平道路（行）和垂直道路（列）的数量。接下来是 $N$ 行。其中第 $i$ 行包含关于第 $i$ 行交叉口的信息，第 0 行是最北端的行。每一行包含 $3M$ 个整数，以空格分隔，格式如下：

S_{i,0} W_{i,0} T_{i,0} S_{i,1} W_{i,1} T_{i,1}... S_{i,M-1} W_{i,M-1} T_{i,M-1}

$S_{i,j}$、$W_{i,j}$ 和 $T_{i,j}$ 均指代从北数第 $i$ 行、从西数第 $j$ 列的交叉口。

输出格式

对于每个测试用例，输出一行，包含文本 "Case #x: t"，其中 $x$ 是测试用例编号，$t$ 是行人从西南角到达东北角所需的最少分钟数。

数据范围

$C, N, M, S_{i,j}, W_{i,j}, T_{i,j}$ 均为非负整数。 $C \le 100$

小数据范围 (13 分)

$1 \le N, M \le 3$ $0 < S_{i,j}, W_{i,j} \le 10$ $0 \le T_{i,j} \le 20$

大数据范围 (20 分)

$1 \le N, M \le 20$ $0 < S_{i,j}, W_{i,j} \le 10^7$ $0 \le T_{i,j} \le 10^8$

样例

输入 1

2
1 1
3 2 10
1 2
1 5 3 1 5 2

输出 1

Case #1: 4
Case #2: 7

说明

第一个案例描述如上。行人向北穿过（1 分钟），等待 2 分钟，然后向东穿过（1 分钟），总共 4 分钟。 第二个案例如下图所示。行人向东穿过（1 分钟），等待 2 分钟，然后向北穿过（1 分钟）。接着她沿街区向东走（2 分钟）并向东穿过（1 分钟），总共 7 分钟。