#include <cstdio>
#include <cstring>
#include <bitset>

const int MAXN = 1e3;
const int SIGMA = 3e3;

int pi[SIGMA + 1], d[SIGMA + 1], len[SIGMA + 1];
char s[SIGMA + 2], c[SIGMA + 1];
bool mt[MAXN + 1][SIGMA + 1];

static inline int min(int a, int b) {
  return a > b ? b : a;
}

int main() {
  int t, n, m, k, q, z, l;
  FILE *fin = fopen("carte.in", "r");
  l = 1;
  fscanf(fin, "%d", &t);
  FILE *fout = fopen("carte.out", "w");
  for (; t > 0; --t) {            
    fscanf(fin, "%s%d", c + 1, &n);
    z = strlen(c + 1);
    for (int i = 0; i < n; ++i) {
      fscanf(fin, "%s\n", s + 1);
      m = strlen(s + 1);
      k = pi[1] = 0;
      for (q = 2; q <= m; ++q) {
        while (k > 0 && s[q] != s[k + 1]) {
          k = pi[k];
        }
        if (s[q] == s[k + 1]) {
          ++k;
        }
        pi[q] = k;
      }
      q = 0;
      for (int j = 1; j <= z; ++j) {
        while (q > 0 && s[q + 1] != c[j]) {
          q = pi[q];
        }
        if (s[q + 1] == c[j]) {
          ++q;
        }
        if (q == m) {
          mt[l][j] = 1; 
        } else {
          mt[l][j] = 0;
        }
      }
      len[l++] = strlen(s + 1);
    }
    d[0] = 0;
    for (int i = 1; i <= z; ++i) {
      d[i] = d[i - 1] + 1;
      for (int j = 1; j <= n; ++j) {
        if (mt[j][i] && i - len[j] >= 0) {
          d[i] = min(d[i], d[i - len[j]]);
        }
      }
    }
    fprintf(fout, "%d\n", d[z]);
  }
  fclose(fin);
  fclose(fout);
  return 0;
}