#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 dis = [&](int x0, int y0, int x1, int y1) -> int { return max(abs(x0 - x1) - 1, abs(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 = 1; j <= k; j ++) if (i != j) {
                auto [x0_, y0_, x1_, y1_] = a[j]; int w;
                if ((y0_ <= y0 && y0 <= y1_) || (y0_ <= y1 && y1 <= y1_))
                    w = min(abs(x0 - x1_), abs(x1 - x0_)) - 1;
                else if ((x0_ <= x0 && x0 <= x1_) || (x0_ <= x1 && x1 <= x1_))
                    w = min(abs(y0 - y1_), abs(y1 - y0_)) - 1;
                else w = min(min(dis(x0, y0, x1_, y1_), dis(x0, y1, x1_, y0)), min(dis(x1, y1, x0_, y0_), dis(x1, y0, x0_, y1_)));
                // cout << i << ' ' << j << ':' << w << '\n';
                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
*/