#include <bits/stdc++.h>
bool MemoryST; using namespace std;
#define ll long long
#define mk make_pair
#define open(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define abs(x) (((x) > (0)) ? (x) : (-(x)))
#define lowbit(x) ((x) & (-(x)))
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
#define BCNT __builtin_popcount
#define cost_time (1e3 * clock() / CLOCKS_PER_SEC)
#define cost_space (abs(&MemoryST - &MemoryED) / 1024.0 / 1024.0) << "MB"
const ll inf = 1e18; 
mt19937 rnd(random_device{}());
const int maxn = 1005;
int T, n, m, k, st, ed;
struct Matrix {
    int x0, y0, x1, y1;
} a[maxn]; namespace Graph {
    struct Edge { int to, nxt, val; } e[maxn * maxn << 1];
    int head[maxn], ecnt = 0;
    void addEdge(int u, int v, int w) { e[++ ecnt] = Edge { v, head[u], w }, head[u] = ecnt; }
} using namespace Graph;
priority_queue<pair<ll, int> >q; ll dis[maxn]; bool vis[maxn];
void work() {
    for (int i = st; i <= ed; i ++) dis[i] = inf, vis[i] = 0;
    dis[st] = 0, q.push(mk(0, st));
    while (!q.empty()) {
        int u = q.top().second; q.pop();
        if (vis[u]) continue; vis[u] = 1;
        // cout << u << ' ' << dis[u] << '\n';
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].to, w = e[i].val;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (!vis[v]) q.push(mk(-dis[v], v));
            }
        }
    }
}
bool MemoryED; int main() {
    auto chkmin = [&](int &a, int b) -> void { a = min(a, b); };
    auto disX = [&](int x0, int x1, int _x0, int _x1) -> int {
        if (x0 <= _x1 && _x0 <= x1) return 0;
        if (x1 < _x0) return _x0 - x1 - 1;
        return x0 - _x1 - 1;
    }; auto disY = [&](int y0, int y1, int _y0, int _y1) -> int {
        if (y0 <= _y1 && _y0 <= y1) return 0;
        if (y1 < _y0) return _y0 - y1 - 1;
        return y0 - _y1 - 1;
    }; 
    scanf("%d", &T); for (int NOW_TEST = 1; NOW_TEST <= T; NOW_TEST ++) {
        scanf("%d %d %d", &m, &n, &k), st = 0, ed = k + 1, ecnt = 0;
        memset(head, 0, sizeof(head));
        for (int i = 1; i <= k; i ++) 
            scanf("%d %d %d %d", &a[i].x0, &a[i].y0, &a[i].x1, &a[i].y1);
        addEdge(st, ed, m);
        for (int i = 1; i <= k; i ++) {
            auto [x0, y0, x1, y1] = a[i];
            addEdge(st, i, x0), addEdge(i, ed, m - x1 - 1);
            for (int j = i + 1; j <= k; j ++) {
                auto [x0_, y0_, x1_, y1_] = a[j]; 
                int w = max(disX(x0, x1, x0_, x1_), disY(y0, y1, y0_, y1_));
                addEdge(i, j, w), addEdge(j, i, w);
            }
        } work(), printf("Case #%d: %lld\n", NOW_TEST, ::dis[ed]);
    }
    return 0;
}
/*
1
100 500 9
8 17 39 311
95 254 96 388
15 340 33 396
55 202 91 268
41 88 47 108
60 375 82 425
59 54 79 113
50 65 54 490
74 288 91 305
*/