import scala.collection.mutable
import scala.io.StdIn._
object Main extends App {
  for (i ← 1 to readInt) {
    val Array(w, h) = readLine.trim.split(' ').map(_.toInt)
    val well = Array.tabulate(h){_ ⇒ readLine.trim.split(' ').map(_.toInt)}
    val nodes = Array.fill(w * h + 2){Nil: List[Edge]}
    val source = w * h
    val sink = source + 1
    val sum = well.map{_.sum}.sum
    for (x ← 0 until w; y ← 0 until h) {
      if ((x + y) % 2 == 0) {
        nodes(source) ::= Edge(y * w + x, well(y)(x))
        nodes(y * w + x) ::= Edge(source, 0)
        nodes(source).head.pair = nodes(y * w + x).head
        nodes(y * w + x).head.pair = nodes(source).head
        for (Coordinate(ox, oy) ← Coordinate(x, y).neighbor if (0 until h).contains(oy) && (0 until w).contains(ox)) {
          nodes(y * w + x) ::= Edge(oy * w + ox, sum)
          nodes(oy * w + ox) ::= Edge(y * w + x, 0)
          nodes(y * w + x).head.pair = nodes(oy * w + ox).head
          nodes(oy * w + ox).head.pair = nodes(y * w + x).head
        }
      }else {
        nodes(sink) ::= Edge(y * w + x, 0)
        nodes(y * w + x) ::= Edge(sink, well(y)(x))
        nodes(sink).head.pair = nodes(y * w + x).head
        nodes(y * w + x).head.pair = nodes(sink).head
      }
    }
    var flow = 0
    var hasFlow = true
    val depth = Array.fill(h * w + 2){-1}
    val searching = Array.fill(h * w + 2){Nil: List[Edge]}
    while(hasFlow){
      hasFlow = false
      bfs(nodes, depth, searching, source, sink)
      var f = dfs(source, sink, depth, searching)
      while (f != 0){
        hasFlow = true
        flow += f
        f = dfs(source, sink, depth, searching)
      }
    }
    println(s"Case $i: ${sum - flow}")
  }

  def bfs(nodes: Array[List[Edge]], depth: Array[Int], searching: Array[List[Edge]], source: Int, sink: Int): Unit = {
    val queue = mutable.Queue[Int](source)
    depth.indices.foreach(i ⇒ depth(i) = -1)
    depth(source) = 0
    searching.indices.foreach(i ⇒ searching(i) = nodes(i))
    while (queue.nonEmpty) {
      val current = queue.dequeue()
      for (Edge(to, flow) ← nodes(current) if flow > 0 && depth(to) == -1) {
        depth(to) = depth(current) + 1
        queue.enqueue(to)
      }
    }
  }
  def dfs(current: Int, sink: Int, depth: Array[Int], searching: Array[List[Edge]], minFlow: Int = Int.MaxValue): Int = {
    if (current == sink) minFlow
    else {
      var result = 0
      while (result == 0 && searching(current).nonEmpty) {
        searching(current) match {
          case (e@Edge(to, flow))::r if flow > 0 && depth(to) > depth(current) ⇒
            result = dfs(to, sink, depth, searching, math.min(flow, minFlow))
            if (result != 0){
              e.flow -= result
              e.pair.flow += result
            }else {
              searching(current) = r
            }
          case _::r ⇒ searching(current) = r
          case Nil ⇒ ???
        }
      }
      result
    }
  }

  case class Edge(to: Int, var flow: Int) {
    private var mPair: Option[Edge] = None
    def pair: Edge = mPair.get
    def pair_=(that: Edge) = mPair = Some(that)
  }
  case class Coordinate(x: Int, y: Int) {
    def neighbor: List[Coordinate] = List(Coordinate(x + 1, y), Coordinate(x - 1, y), Coordinate(x, y + 1), Coordinate(x, y - 1))
  }
}
