#include <stdio.h>

char s[16][101];
int a[16][16];
int col[16];
int n, maxcolor;

char close (int i, int j)
{
  int p, q;
  int mismatchl[102], mismatchr[102];

  if (strlen(s[i]) > strlen(s[j]))
    { int k = i; i = j; j = k; }
  if (strlen(s[i]) == strlen(s[j]))
    {
      int mismatch = 0;
      for (p = 0; p < strlen(s[i]); p ++)
	if (toupper(s[i][p]) != toupper(s[j][p])) mismatch ++;
      return (mismatch <= 1);
    }
  else if (strlen(s[i]) == strlen(s[j]) -1)
    {
      int mismatch = 0;
      for (p = 0, q = 0; p < strlen(s[i]) && q < strlen(s[j]); p++, q++)
	if (toupper(s[i][p]) != toupper(s[j][q])) { mismatch ++; p ++; }
      return (mismatch <= 1);
    }
  else return 0;
}

void colors (int p, int c)
{
  int i, j;

  if (p < n)
    {
      col[p] = c;
      for (i = 1; i < maxcolor && i <= p+1; i ++)
	{
	  char possible = 1;
	  for (j = 1; j <= p && possible; j ++)
	    if (a[j][p+1] == 1 && col[j] == i)
	      possible = 0;
	  if (possible) colors (p+1, i);
	}
    }
  else 
    {
      int mc = 0;
      col[p] = c;
      for (j = 1; j <= n; j ++)
	if (col[j] > mc) mc = col[j];
      if (mc < maxcolor) maxcolor = mc;
    }
}

int main (void)
{
  int k, K;
  int i, j;

  FILE *in = fopen ("friends.in", "r");
  fscanf (in, "%d\n", &K);
  for (k = 1; k <= K; k ++)
    {
      fscanf (in, "%d\n", &n);
      for (i = 1; i <= n; i ++)
	for (j = 1; j <= n; j ++)
	  a[i][j] = 1;
      for (i = 1; i <= n; i ++)
	{
	  fgets (s[i], 101, in); s[i][strlen(s[i])-1] = 0; 
	  for (j = 1; j < i; j ++)
	    if (close (i,j)) a[i][j] = a[j][i] = 0;
	}
      printf ("Data Set %d:\n", k);
      maxcolor = n+1; colors (1,1);
      printf ("%d\n", maxcolor);
    }
  fclose (in);
  return 0;
}