#include <bits/stdc++.h>

using namespace std;

constexpr int MAX_N = 5200;
constexpr int SIGMA = 10;
constexpr int NIL = -1;

int to[MAX_N][SIGMA];
bool finalState[MAX_N];
bool distinct[MAX_N][MAX_N];

char *data;
int dataPtr;

void readInput() {
  FILE *f = fopen("robo.in", "r");
  fseek(f, 0, SEEK_END);
  int m_size = ftell(f);
  rewind(f);

  data = (char *) malloc(m_size + 1);
  fread(data, 1, m_size, f);
  fclose(f);

  data[m_size] = 0;
}

void clearInput() { // mlc
  int i = 1;
  int ptr = 1;
  while (data[i]) {
    if (not(isspace(data[ptr - 1]) and isspace(data[i])))
      data[ptr++] = data[i];
    i += 1;
  }
}

int readInt() {
  while (!isdigit(data[dataPtr]) and data[dataPtr])
    dataPtr += 1;
  if (data[dataPtr] == 0)
    return NIL;
  int q = 0;
  while (isdigit(data[dataPtr])) {
    q = (q << 1) + (q << 3) + (data[dataPtr] - '0');
    dataPtr += 1;
  }
  return q;
}

bool readEdge(int &node1, int &node2, char &c) {
  int tmp = dataPtr;
  node1 = readInt();
  if (node1 == NIL)
    return false;
  int pos = dataPtr;
  while ((not(isdigit(data[pos])) and data[pos]) and not(isalpha(data[pos])))
    pos += 1;
  if (!isalpha(data[pos])) {
    dataPtr = tmp;
    return false;
  } else {
    c = data[pos];
    node2 = readInt();
    return true;
  }
}

int unreachableStates(const int n, const int sigma) {
  static int Q[MAX_N];
  static bool color[MAX_N];
  int qStart = 0, qEnd = 1;

  memset(color, 0, n);
  Q[0] = 1;
  color[0] = 1;

  while (qStart != qEnd) {
    const int u = Q[qStart++];
    for (int i = 0; i < sigma; i += 1) {
      const int v = to[u][i];
      if (color[v] == false) {
        color[v] = true;
        Q[qEnd++] = v;
      }
    }
  }
  return n - qEnd;
}

void dump(const int n) {
  for (int i = 0; i < n; i += 1)
    for (int j = 0; j < n; j += 1)
      printf("%d%c", distinct[i][j], " \n"[j == n - 1]);
}

int dfaMinimization(const int n,
                          const int sigma) {
  for (int i = 0; i < n; i += 1)
    for (int j = 0; j < n; j += 1)
      if (finalState[i] != finalState[j])
        distinct[i][j] = true;

  bool changed;
  do {
    changed = 0;
    for (int i = 0; i < n; i += 1)
      for (int j = i + 1; j < n; j += 1)
        if (distinct[i][j] == false) {
          int k = 0;
          while ((k < sigma) and (to[i][k] == NIL or to[j][k] == NIL or not(distinct[to[i][k]][to[j][k]])))
            k += 1;
          if (k != sigma) {
            distinct[i][j] = distinct[j][i] = true;
            changed = true;
          }
        }

  } while (changed);



  static int root[MAX_N];
   for (int i = 0; i < n; i += 1)
    root[i] = i;

  srand(time(0));

  auto getRoot = [] (int u) -> int {
    int r = u;
    while (r != root[r])
      r = root[r];
    while (u != root[u]) {
      int v = root[u];
      root[u] = r;
      u = v;
    }
    return r;
  };

  for (int i = 0; i < n; i += 1)
    for (int j = i + 1; j < n; j += 1) {
      if (distinct[i][j] == false) {
        int u = getRoot(i);
        int v = getRoot(j);
        if (u != v) {
          if (rand() & 1)
            root[v] = u;
          else
            root[u] = v;
        }
      }
    }

  int numErased = 0;
  for (int i = 0; i < n; i += 1)
    numErased += root[i] != i;
  return n - numErased;
}

int main() {
  readInput();
  clearInput();

  FILE *f = fopen("robo.out", "w");

  int numTests = readInt();
  while (numTests--) {
    int n = readInt(), sigma = readInt();

    for (int i = 0; i < n; i += 1) {
      finalState[i] = false;
      for (int j = 0; j < sigma; j += 1)
        to[i][j] = NIL;
      for (int j = 0; j < n; j += 1)
        distinct[i][j] = 0;
    }

    int pos;
    do {
      finalState[readInt()] = 1;
      pos = dataPtr;
      while ((!isdigit(pos) and data[pos])
             and data[pos] != '\n')
        pos += 1;
    } while (data[pos] != '\n');

    vector <pair <pair <int, int>, char>> T;
    map <char, int> normalize;
    int u, v; char ch;
    while (readEdge(u, v, ch)) {
      T.push_back(make_pair(make_pair(u, v), ch));
      normalize[ch] = 1;
    }
    pos = 0;
    for (map <char, int> :: iterator it = normalize.begin(); it != normalize.end(); it++) {
      normalize[it->first] = pos;
      pos += 1;
    }
    assert(pos <= sigma);
    for (const auto &edge : T) {
      to[edge.first.first][normalize[edge.second]] = edge.first.second;
    }
    fprintf(f, "%d\n", dfaMinimization(n, sigma));
  }
  fclose(f);
  return 0;
}