#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<map>

#include<set>

#include<vector>

#include<stack>

#include<queue>



using namespace std;

const int MOD=1000000007;

const int N=105;

const int M=5000005;

struct node

{

    char dread[20];

    char M;

}q[M];

int f[20];

int k1[N],k2[N],k3[N];

int ans,cnt;

int n,m,k;

int qt[M],L,R;

int bfs(char *dread)

{

    for(int i=0;i<n;++i)

    q[cnt].dread[i]=dread[i];

    q[cnt].M=0;

    L=R=0;

    qt[R++]=cnt++;

    int l=0,W;

    while(L<R)

    {

        int x=qt[L++];

        l=q[x].M;

        if(l==k) return l;

        if(cnt>=M) continue;

        W=1;

        q[cnt].M=q[x].M+1;

        for(int i=0;i<n;++i)

        {

            if(i==k1[l+1])

            q[cnt].dread[i]=max(q[x].dread[i]-2,1);

            else if(i==k2[l+1]||i==k3[l+1])

            q[cnt].dread[i]=q[x].dread[i]+2;

            else if(f[i]==f[k2[l+1]]||f[i]==f[k3[l+1]])

            q[cnt].dread[i]=q[x].dread[i]+1;

            else

            q[cnt].dread[i]=q[x].dread[i];

            if(q[cnt].dread[i]>W)

            W=q[cnt].dread[i];

            if(W>5) break;

        }

        if(W<=5)

        qt[R++]=cnt++;

        if(cnt>=M) continue;



        W=1;

        q[cnt].M=q[x].M+1;

        for(int i=0;i<n;++i)

        {

            if(i==k2[l+1])

            q[cnt].dread[i]=max(q[x].dread[i]-2,1);

            else if(i==k1[l+1]||i==k3[l+1])

            q[cnt].dread[i]=q[x].dread[i]+2;

            else if(f[i]==f[k1[l+1]]||f[i]==f[k3[l+1]])

            q[cnt].dread[i]=q[x].dread[i]+1;

            else

            q[cnt].dread[i]=q[x].dread[i];

            if(q[cnt].dread[i]>W)

            W=q[cnt].dread[i];

            if(W>5) break;

        }

        if(W<=5)

        qt[R++]=cnt++;

        if(cnt>=M) continue;



        W=1;

        q[cnt].M=l+1;

        for(int i=0;i<n;++i)

        {

            if(i==k3[l+1])

            q[cnt].dread[i]=max(q[x].dread[i]-2,1);

            else if(i==k2[l+1]||i==k1[l+1])

            q[cnt].dread[i]=q[x].dread[i]+2;

            else if(f[i]==f[k2[l+1]]||f[i]==f[k1[l+1]])

            q[cnt].dread[i]=q[x].dread[i]+1;

            else

            q[cnt].dread[i]=q[x].dread[i];

            if(q[cnt].dread[i]>W)

            W=q[cnt].dread[i];

            if(W>5) break;

        }

        if(W<=5)

        qt[R++]=cnt++;



    }

    return l;

}

int main()

{

    //freopen("data.in","r",stdin);

    int T;

    scanf("%d",&T);

    for(int w=1;w<=T;++w)

    {

        printf("Case #%d: ",w);

        char dread[20];

        scanf("%d %d %d",&n,&m,&k);

        for(int i=0;i<n;++i)

        scanf("%d",&f[i]);

        for(int i=0;i<n;++i)

        scanf("%d",&dread[i]);

        for(int i=1;i<=k;++i)

        scanf("%d %d %d",&k1[i],&k2[i],&k3[i]);

        ans=0;

        cnt=0;

        printf("%d\n",bfs(dread));

    }

    return 0;

}