Description

You have a painting. It is represented by an n m grid, each square is painted color (R,G,B). Your task is to destroying it by repainting every square red (255,0,0), green (0,255,0) or blue (0,0,255). Every square should be repainted (though it may be repainted the same color as before). The cost of repainting (R1,G1,B1) to (R2,G2,B2) is the hamming distance between two colors, i.e. |R1-R2|+|G1-G2|+|B1-B2|. For example, repainting (12,34,56) to R costs 255-12+34+56=333. You want to make the resulting paint look ugly, so if the resulting painting has R reds, G greens and B blues, max{R,G,B}-min{R,G,B} should be minimized. Under this condition, the total cost should be as small as possible.

Input

The first line contains a single integer T (1 T 50), the number of test cases. Each test case begins with two numbers n and m, the dimensions of the painting. (1 n, m 20) The next n lines describe the initial painting. Each grid is represented by (R,G,B), with no spaces inside. (0 R,G,B 255) Each pair of consecutive squares are separated by exactly one space.

Output

For each test case, print the case number and the minimal cost.

Sample Input

3 3 3 (255,0,0) (0,255,0) (0,0,255) (0,255,0) (255,0,0) (0,0,255) (0,0,255) (0,255,0) (255,0,0) 2 2 (0,0,0) (0,0,0) (0,0,0) (0,0,0) 5 2 (205,140,120) (216,125,179) (210,162,235) (149,155,218) (231,144,233) (160,230,185) (160,105,98) (157,148,185) (163,171,237) (211,157,145)

Sample Output

Case 1: 0 Case 2: 1020 Case 3: 3706

Source

The 32nd ACM-ICPC Beijing First Round Internet Contest