use std::{
    cmp::Reverse,
    collections::BinaryHeap,
    io::{stdin, Read},
    usize,
};

fn diff(a: usize, b: usize) -> usize {
    a.max(b) - a.min(b)
}

fn main() {
    let mut input = String::new();
    stdin().lock().read_to_string(&mut input).unwrap();
    let mut ints = input
        .split_ascii_whitespace()
        .map(|i| i.parse::<usize>().unwrap());
    let mut get = || ints.next().unwrap();

    for case in 1..=get() {
        let (n, p) = (get(), get());
        let xs = (0..n)
            .map(|_| {
                let (mut min, mut max) = (usize::MAX, 0);
                for _ in 0..p {
                    let x = get();
                    min = min.min(x);
                    max = max.max(x);
                }
                (min, max)
            })
            .collect::<Vec<(_, _)>>();

        let mut q = BinaryHeap::new();
        q.push((Reverse(0), 0, 0));
        while let Some((Reverse(dist), i, v)) = q.pop() {
            // eprintln!("dist = {}; i = {}; v = {}", dist, i, v);
            if i == n {
                println!("Case #{}: {}", case, dist);
                break;
            }
            let (min, max) = xs[i];

            let dist_a = dist + diff(v, min) + diff(min, max);
            q.push((Reverse(dist_a), i + 1, max));
            let dist_b = dist + diff(v, max) + diff(max, min);
            q.push((Reverse(dist_b), i + 1, min));
        }
    }
}