#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5+5;

ll t;
ll x[N],ans;

void solve (ll n, ll m, ll v)
{
    ll c[N]={0},d[N]={0};
    ll a[N]={0},b[N]={0};
    for (ll i = 1; i <= m; i++)
    {
        scanf ("%lld%lld", &c[i],&d[i]);
    }

    for (ll i = 1; i <= v; i++)
    {
        a[i] = i, b[i] = i;
    }

    for (ll i = 1; i <= m; i++) // no_s
    {
        if (x[c[i]] == 0)
        {
            x[c[i]] = d[i];
        }else
        {
            if (x[c[i]] != d[i])
            printf ("0\n"); return;
        }
    }

    for (ll i = 1; i <= v; i++) // have_s
    {
        if (x[a[i]] == b[i])
        {
            ans ++;
        }else
        {
            continue;
        }
    }printf ("%lld\n", ans);
}

int main()
{
    freopen ("assign.in","r",stdin);
    freopen ("assign.out","w",stdout);
    scanf ("%lld", &t);
    while (t--)
    {
        ll n,m,v;
        scanf ("%lld %lld %lld", &n,&m,&v);
        solve (n, m, v);
        ans = 0;
    }
    fclose (stdin);
    fclose (stdout);
    return 0;
}