Where roads intersect, there are often traffic lights that tell pedestrians (people walking) when they should cross the street. A clever pedestrian may try to optimize her path through a city based on when those lights turn green.

The city in this problem is a grid, $N$ rows tall by $M$ columns wide. Our pedestrian wants to get from the northeast corner of the southwest block to the southwest corner of the northeast block. Your objective is to help her find her way from corner to corner in the fastest way possible.

The pedestrian can cross a street in 1 minute, but only if the traffic light is green for the entire crossing. The pedestrian can move between two streets, along one edge of a block, in 2 minutes. The pedestrian can only move along the edges of the block; she cannot move diagonally from one corner of a block to the opposite corner.

Traffic lights follow the following pattern: at intersection $i$, the north-south lights stay green for $S_i$ minutes, while the east-west lights stay red. Then the north-south lights turn red, the east-west lights turn green, and they stay that way for $W_i$ minutes. Then they start the same cycle again. The pedestrian starts moving at t=0 minutes; traffic light i starts a cycle by turning green in the north-south direction at $t=T_i$ minutes. There are cycles before $t=T_i$ as well.

For example, intersection 0 could have the following values:

$${\displaystyle S_0=3,W_0=2,T_0=0}$$

The north-south direction turns green after 0 minutes. That lasts 3 minutes, during which time the pedestrian can cross in the north-south direction and not the east-west direction. Then the lights switch, and for the next 2 minutes the pedestrian can cross in the east-west direction and not the north-south direction. Then, 5 minutes after it started, the cycle starts again. This is exactly the same as the following configuration:

$${\displaystyle S_0=3,W_0=2,T_0=10}$$

Input Specification

The first line in the input contains the number of test cases, $C$. This is followed by $C$ test cases in the following format:

A single line containing N M, where $N$ and $M$ are the number of horizontal roads (rows) and vertical roads (columns), as above. This is followed by $N$ lines. The $i^{\text{th}}$ of those lines contains information about intersections on the $i^{\text{th}}$ row, where the $0^{\text{th}}$ row is the northmost. Each of those lines will contain $3M$ integers, separated by spaces, in the following form:

$${\displaystyle S_{i,0}{W}_{i,0}{T}_{i,0}{S}_{i,1}{W}_{i,1}{T}_{i,1}\dots S_{i,M-1}{W}_{i,M-1}{T}_{i,M-1}}$$

$S_{i,j}$, $W_{i,j}$ and $T_{i,j}$ all refer to the intersection in the $i^{\text{th}}$ row from the north and the $j^{\text{th}}$ column from the west.

Output Specification

For each test case, output a single line containing the text Case #x: t, where $x$ is the number of the test case and $t$ is the minimum number of minutes it takes the pedestrian to get from the southwest corner to the northeast corner.

Limits

Time limit: 30 seconds per test set.

Memory limit: 1 GB.

$C$, $N$, $M$, $S_{i,j}$, $W_{i,j}$, $T_{i,j}$ are all non-negative integers.

$C\le 100$

Small Dataset

$1\le N,M\le 3$

$0<S_{i,j},W_{i,j}\le 10$

$0\le T_{i,j}\le 20$

Large Dataset

$1\le N,M\le 20$

$0<S_{i,j},W_{i,j}\le {10}^7$

$0\le T_{i,j}\le {10}^8$

Sample Input

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

Sample Output

Case #1: 4
Case #2: 7

Explanation for Sample

The first case is described above. The pedestrian crosses to the North (1 minute), waits 2 minutes and then crosses to the East (1 minute), for a total of 4 minutes.

The second case is depicted in the diagram below. The pedestrian crosses to the East (1 minute), waits 2 minutes and crosses to the North (1 minute). Then she walks east a block (2 minutes) and crosses to the East (1 minute) for a total of 7 minutes.