All Submissions


Nilay has decided to plant trees in his garden area. He has done a preliminary survey and he created a detailed grid map of the area which indicates the nutrition value of the soil.

He is now planning to plant trees on several grid blocks according this map, but he decided not to place any two plants on adjacent positions to avoid any resource competetion between plants. Two blocks are considered to be adjacent when they have a common edge. You are one of the programmers working for Nilay and your task is to write a program which calculates the maximum amount of nutrition value used, given the map of the garden.

INPUT

The first line of the input specifies N, the number of test cases. Then N test cases follow, each of which looks like the following:

W H
r1,1 r2,1 ... rW,1
...
r1,H r2,H ... rW,H

The first line of a test case contains two integers W and H in range of [1,20]. They specifies the dimension of the garden. The next H lines, each of which contains W integers, represent the map of the area. Each integer rx,y [0,10000] indicates the nutrition content of the soil at the grid block (x, y).

OUTPUT

For each test case, output the case number (starting from 1) and the maximum possible amount of nutrition content used. Refer to the sample output section about the format.

Sample Input


2
2 2
2 3
3 5
3 2
4 1 1
2 1 4


Sample Output


Case 1: 7
Case 2: 8


Vivek Keshri

Languages: C,C++,C#,Java,JavaScript,Pascal,Perl,PHP,Python,Ruby

Time Limit: 3 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0