#include<stdio.h>
  #include<stdlib.h>


  int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

  int main()
  { int t,m,n,x,y,s;
	 int array[1000];
	 scanf("%d",&t);
	 for(int i=0;i<t;i++)
		 { scanf("\n");
			scanf("%d %d",&m,&n);
			for(s=0;s<1000;s++)array[s]=0;
			for(int p=0;p<n;p++)
				 { scanf("%d %d",&x,&y);
					array[x-1]++;
					array[y-1]++;
				  }


			qsort (array,1000, sizeof(int), compare);
			printf("Case %d: %d\n",i+1,array[1000-m]);
			}
			return 0;
			}