#include<cstdio>
#include<iostream>

using namespace std;

const int maxn =5e3+5;
const int maxm =21;
const int log2maxn =15;

int n,m,inf;
struct matrixType
{
    int mp[maxm][maxm];
    void setE()
    {
        int i,j;
        for(i=1;i<=m;i++)
            for(j=1;j<=m;j++)
                mp[i][j]=(i==j);
    }
}dp[maxn][log2maxn];
int act[maxn][log2maxn];

void multiple(matrixType& a,matrixType &b,matrixType* c)
{
    int i,j,k;
    int tmp;
    for(i=1;i<=m;i++)
    {
        //puts("orz");
        for(j=1;j<=m;j++)
        {
            c->mp[i][j] = 0;
            //printf("%d %d\n", i, j);
            for(k=1;k<=m;k++)
            {
                if (b.mp[k][j]==0||a.mp[i][k]<=inf/b.mp[k][j])
                    tmp=a.mp[i][k]*b.mp[k][j];
                else tmp=inf+1;
                c->mp[i][j]+=tmp;
                if (c->mp[i][j]>inf)
                    c->mp[i][j]=inf+1;
                
            }
        }
    }
}

matrixType qhy,tmpQ;

void standing_by()
{
    int i,j,k,L;
    int u,v;
    scanf("%d%d%d",&n,&m,&inf);
    //printf("%d%d%d",n,m,k);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&L);
        for(j=1;j<=L;j++)
        {
            scanf("%d %d",&u,&v);
            dp[i][0].mp[u][v]=1;
        }
        for(j=1;j<=m;j++)
            dp[i][0].mp[j][j]=1;
    }

    for(i=n-1;i>=1;i--)
    {
        //printf("%d\n",i);
        for(j=1;i+(1<<j)<=n+1;j++)
        {
            //printf("%d %d %d %d\n", j,i, i + (1 << j), i + (1 << (j - 1)));
            multiple(dp[i][j-1],dp[i+(1<<(j-1))][j-1],&dp[i][j]);
        }
    }

    int r,c;
    int ans=0;

    for(i=1;i<=n;i++)
    {
        qhy.setE();
        for(j=log2maxn-1,k=i;j>=0;j--)
        {
            if (k+(1<<j)>n+1) continue;
            multiple(qhy,dp[k][j],&tmpQ);
            if (tmpQ.mp[1][m]<=inf)
            {
                k+=(1<<j);
                for(r=1;r<=m;r++)
                    for(c=1;c<=m;c++)
                        qhy.mp[r][c]=tmpQ.mp[r][c];
            }
        }
        ans=max(ans,k-i);
    }

    printf("%d\n",ans);
}

void complete()
{

}

int main()
{
#ifdef TanJI
    freopen("D:\\Cpp\\1.in", "r", stdin);
    //freopen("D:\\Cpp\\1.out", "w", stdout);
#endif

    int t;
    scanf("%d",&t);
    for(;t;t--)
    {
        standing_by();
        complete();
    }
    return 0;
}