{-# LANGUAGE BangPatterns #-}
import Data.Array
import Control.Monad (liftM, forM_)
import Text.Printf

import Debug.Trace

type Time = Int
data LightState = NS | EW deriving (Show)
type LightConf = (Int,Int,Time)
type TestCase = Array (Int,Int) LightConf

solve :: TestCase -> Time
solve c = table ! snd (bounds table)
  where table = solve' c

solve' :: TestCase -> Array (Int,Int) Time
solve' c = h c table
  where
    ((1,1), (x1,y1)) = bounds c
    b = ((1,1), (x1*2,y1*2))
    table = array b [(i, f i) | i <- range b]
    f (1,1) = 0
    f (x,y) =
      minimum $
        [ (table ! (x-1, y)) + 2 | odd x, x /= 1 ] ++
        [ (table ! (x, y-1)) + 2 | odd y, y /= 1 ] ++
        [ tm (c ! g x y) EW (table ! (x-1, y)) + 1 | even x ] ++
        [ tm (c ! g x y) NS (table ! (x, y-1)) + 1 | even y ]
    g x y = ((x+1) `div` 2, (y+1) `div` 2)

h :: TestCase -> Array (Int,Int) Time -> Array (Int,Int) Time
h c table
  | table==table2 = table
  | otherwise = h c table2
  where table2 = refine c table

refine :: TestCase -> Array (Int,Int) Time -> Array (Int,Int) Time
refine c table = table2
  where
    b@(_, (x1,y1)) = bounds table
    table2 = array b [(i, f i) | i <- range b]
    f (x,y) =
      minimum $
        (table ! (x,y)) :
        [ (table ! (x-1, y)) + 2 | odd x, x /= 1 ] ++
        [ (table ! (x, y-1)) + 2 | odd y, y /= 1 ] ++
        [ tm (c ! g x y) EW (table ! (x-1, y)) + 1 | even x ] ++
        [ tm (c ! g x y) NS (table ! (x, y-1)) + 1 | even y ] ++
        [ (table ! (x+1, y)) + 2 | even x, x/=x1 ] ++
        [ (table ! (x, y+1)) + 2 | even y, y/=y1 ] ++
        [ tm (c ! g x y) EW (table ! (x+1, y)) + 1 | odd x ] ++
        [ tm (c ! g x y) NS (table ! (x, y+1)) + 1 | odd y ]
    g x y = ((x+1) `div` 2, (y+1) `div` 2)

tm :: LightConf -> LightState -> Time -> Time
tm (s,w,t0) NS t = f s w t0 t
tm (s,w,t0) EW t = f w s (t0+s) t

f :: Int -> Int -> Time -> Time -> Time
f ok ng t0 t = if t < t1+ok then t else t1+n
  where
    n = ok+ng
    t1 = if t0 <= t
         then t0 + ((t-t0) `div` n) * n
         else t0 - ((((t0-t) `div` n) + 1) * n)

readTestCase :: IO TestCase
readTestCase = do
  [n,m] <- liftM (map read . words) getLine
  rows <- sequence $ replicate n $ liftM (group3 . map read . words) getLine  
  return $ array ((1,1),(m,n)) $ do
    (y,row) <- zip [n,n-1..] rows
    (x,l) <- zip [1..] row
    return ((x,y),l)
  where
    group3 [] = []
    group3 (a:b:c:xs) = (a,b,c) : group3 xs
    group3 _ = undefined

main :: IO ()
main = do
  c <- liftM read getLine
  forM_ [(1::Int)..c] $ \i -> do
    testcase <- readTestCase
    printf "Case #%d: %d\n" i (solve testcase)