#include <map>

#include <set>

#include <ctime>

#include <cmath>

#include <queue>

#include <stack>

#include <vector>

#include <string>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <sstream>

#include <iostream>

#include <algorithm>

#include <functional>

using namespace std;

inline int read(){int now=;register char c=getchar();for(;!isdigit(c);c=getchar());

for(;isdigit(c);now=now*+c-'',c=getchar());return now;}

#define For(i, x, y) for(int i=x;i<=y;i++)

#define _For(i, x, y) for(int i=x;i>=y;i--)

#define Mem(f, x) memset(f,x,sizeof(f))

#define Sca(x) scanf("%d", &x)

#define Sca2(x,y) scanf("%d%d",&x,&y)

#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define Scl(x) scanf("%lld",&x);

#define Pri(x) printf("%d\n", x)

#define Prl(x) printf("%lld\n",x);

#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();

#define LL long long

#define ULL unsigned long long

#define mp make_pair

#define PII pair<int,int>

#define PIL pair<int,long long>

#define PLL pair<long long,long long>

#define pb push_back

#define fi first

#define se second

typedef vector<int> VI;

const double eps = 1e-;

const int maxn = 2e5 + ;

const int maxm = 6e5 + ;

const int INF = 0x3f3f3f3f;

const int mod = 1e9 + ;

struct Dinic{

    struct Edge{

        int from,to,cap,flow,nxt;

        Edge() {}

        Edge(int u,int v,int c,int f,int n):from(u),to(v),cap(c),flow(f),nxt(n) {}

    }edge[maxm];

    int n,s,t,E,head[maxn];

    bool vis[maxn];

    int d[maxn],cur[maxn];

    inline void AddEdge(int f,int t,int c){

        edge[++E] = Edge(f,t,c,,head[f]);

        head[f] = E;

        edge[++E] = Edge(t,f,,,head[t]);

        head[t] = E;

    }

    inline void Init(int n,int s,int t){

        this -> n = n; E = -;

        this -> s = s; head[s] = -;

        this -> t = t; head[t] = -;

        for(int i =  ; i <= n ; i ++) head[i] = -;

    }

    inline bool BFS(){

        memset(vis,,sizeof(vis));

        queue<int>Q;

        d[s] = ;vis[s] = ;

        for(Q.push(s);!Q.empty();){

            int x = Q.front(); Q.pop();

            for(int nxt,i = head[x];~i;i = nxt){

                Edge &e = edge[i]; nxt = e.nxt;

                if(vis[e.to] || e.cap <= e.flow) continue;

                vis[e.to] = ;

                d[e.to] = d[x] + ;

                Q.push(e.to);

            }

        }

        return vis[t];

    }

    inline int DFS(const int &x,int a){

        if(x == t || a == ) return a;

        int flow = ,f,nxt;

        for(int &i = cur[x]; ~i; i = nxt){

            Edge &e = edge[i]; nxt = e.nxt;

            if(d[x] +  != d[e.to]) continue;

            f = DFS(e.to,min(a,e.cap - e.flow));

            if(f <= ) continue;

            e.flow += f;

            edge[i ^ ].flow -= f;

            flow += f; a -= f;

            if(!a) break;

        }

        return flow;

    }

    inline int maxFlow(){return maxFlow(s,t);}

    inline int maxFlow(int s,int t){

        int flow = ;

        for(;BFS();){

            for(int i =  ;i <= n ; i ++) cur[i] = head[i];

            flow += DFS(s,INF);

        }

        return flow;

    }

}g;

int N,M,L,K;

bool MAP[][];

bool check(int x){

    int s =  ,t = N + M *  + ;

    g.Init(t,s,t);

    For(i,,N) g.AddEdge(s,i,x);

    For(i,,N){

        For(j,,M){

            if(MAP[i][j]){

                g.AddEdge(i,j + N,);

            }else{

                g.AddEdge(i,j + N + M,);

            }

        }

    }

    For(i,,M) g.AddEdge(i + N,t,x);

    For(i,,M) g.AddEdge(i + N + M,i + N,K);

    return ((LL)g.maxFlow() >= ((LL)x * N));

}

int solve(){

    int l = ,r = INF;

    int ans = ;

    while(l <= r){

        int m = (l + r) >> ;

        if(check(m)){

            ans = m;

            l = m + ;

        }else{

            r = m - ;

        }

    }

    return ans;

}

int main()

{

    int T; Sca(T);

    int CASE = ;

    while(T--){

        Sca2(N,M); Sca2(L,K); Mem(MAP,);

        For(i,,L){

            int x,y; Sca2(x,y);

            MAP[x][y] = ;

        }

        printf("Case %d: ",CASE++);

        Pri(solve());

    }

    #ifdef VSCode

    system("pause");

    #endif

    return ;

}