#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxN 210
#define MIN(a, b) ((a)<(b)?(a):(b))
#define MAX(a, b) ((a)>(b)?(a):(b))
int g[maxN][maxN];
int limit[maxN][maxN];
int gap[maxN], dist[maxN], pre[maxN], cur[maxN];
int n, nn, m, k, s, t;
int SAP()
{
    int maxflow=0, aug=0xfffffff, u, v;
    memset(g, 0, sizeof(g));
    memset(gap, 0, sizeof(gap));
    memset(dist, 0, sizeof(dist));
    for(int i=0; i<=nn; i++) cur[i] =1;
    u=pre[s]=s; gap[0]=nn;
    while(dist[s]<nn){
    loop:
        for(v=cur[u]; v<=nn; v++) if(g[u][v]<limit[u][v] && dist[u]==dist[v]+1){
            cur[u]=v;
            aug = MIN(aug, limit[u][v] - g[u][v]);
            pre[v]=u;
            u=v;
            if(v == t){
                maxflow+=aug;
                for(u=pre[u]; v!=s; v=u, u=pre[u]){
                    g[u][v]+=aug;
                    g[v][u]-=aug;
                }
                aug=0xfffffff;
            }
            goto loop;
        }
        int mind=nn;
        for(v=1; v<=nn; v++) if((limit[u][v] - g[u][v])>0 && mind>dist[v]){
            mind=dist[v];
            cur[u]=v;
        }
        if(--gap[dist[u]]<=0) break;
        gap[dist[u]=mind+1]++;
        u=pre[u];
    }
    return maxflow;
}
int main()
{
    int i, l, r, mid, a, b, tc;
//    freopen(\"1.txt\", \"r\", stdin);
    scanf(\"%d\", &tc);
    while(tc--){
        scanf(\"%d %d %d\", &n, &m, &k);
        nn=n*2+4;
        memset(limit, 0, sizeof(limit));
        for(i=0; i<m; i++){
            scanf(\"%d %d\", &a, &b);
            limit[a][b+n] = 1;
        }
        for(i=1; i<=n; i++){
            limit[i][2*n+1]=k;
            limit[2*n+2][i+n]=k;
        }
        limit[2*n+1][2*n+2]=0xfffffff;
        s=2*n+3; t=2*n+4;
        l=0; r=n+1;
        while(l<r-1){
            mid = (l+r)>>1;
            for(i=1; i<=n; i++){
                limit[s][i]=mid;
                limit[i+n][t]=mid;
            }
            if(SAP()==n*mid) l=mid;
            else r=mid;
        }
        printf(\"%d\\n\", l);
    }
    return 0;
}