#include <cstdio>

 #include <queue>

 #include<cstring>

 using namespace std;

 struct portal

 {

     int from,to;

 };

 int main()

 {

     int grid[],ggrid[],i,j,D,N,S,L,step=,st,tem,k;

     portal men[];

     scanf("%d",&D);

     while(D--)

     {

         scanf("%d%d%d",&N,&S,&L);

         memset(grid,,sizeof(grid));

         step=;

         for(i=;i<S+L;i++)

             scanf("%d%d",&men[i].from,&men[i].to);

         grid[]=;

         while(grid[N*N]==)

         {

             memcpy(ggrid,grid,sizeof(grid));

             memset(grid,,sizeof(grid));

             for(i=;i<=N*N-;i++)

             {

                 if(ggrid[i])

                 {

                     for(j=;j<=;j++)

                     {

                         st=;

                         tem=i+j;

                         if(tem>N*N)

                             break;

                         for(k=;k<S+L;k++)

                         {

                             if(men[k].from==tem)

                             {

                                 st=;

                                 grid[men[k].to]=;

                                 break;

                             }

                         }

                         if(grid[tem]==&&st==)

                             grid[tem]=;

                     }

                 }

             }

             step++;

         }

         printf("%d\n",step);

     }

 return ;

 }