#include <bits/stdc++.h>

using namespace std;

#define int short

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];
bool color[MAX_N];

char *data;
signed dataPtr;

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

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

  data[m_size] = 0;
}

void clearInput() { // mlc
  signed i = 1;
  signed 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) {
  signed tmp = dataPtr;
  node1 = readInt();
  if (node1 == NIL)
    return false;
  signed 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;
  }
}

void unreachableStates(const int n, const int sigma) {
  static int Q[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;
      }
    }
  }
}

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) {
  unreachableStates(n, sigma);

  for (int i = 0; i < n; i += 1)
    if (color[i])
      for (int j = 0; j < n; j += 1)
        if (color[j] and (finalState[i] != finalState[j]))
          distinct[i][j] = true;

  vector <vector <int>> P;
  vector <int> nodes;
  for (int i = 0; i < n; i += 1) {
    if (color[i]) {
      nodes.push_back(i);
      vector <int> tmp;
      for (int j = i + 1; j < n; j += 1)
        if (color[j] and distinct[i][j] == false)
          tmp.push_back(j);
      P.push_back(tmp);
    }
  }

  bool changed;
  do {
    changed = 0;
    for (int i = 0; i < (int) nodes.size(); i += 1) {
      vector <int> remainders;
      for (const auto &j : P[i]) {
        int k = 0;
        while ((k < sigma) and (to[nodes[i]][k] == NIL
                                or to[j][k] == NIL
                                or not(distinct[to[nodes[i]][k]][to[j][k]]))) {
          k += 1;
        }
        if (k != sigma) {
          distinct[nodes[i]][j] = distinct[j][nodes[i]] = true;
          changed = true;
        } else {
          remainders.push_back(j);
        }
      }
      P[i] = remainders;
    }
  } 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;
  };

  //dump(n);

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

  int ret = 0;
  for (int i = 0; i < n; i += 1)
    ret += (root[i] == i) and color[i];
  return ret;
}

signed 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;
    }

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

    static vector <pair <pair <int, int>, char>> T;
    T.clear();
    static map <char, int> normalize;
    normalize.clear();

    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;
    }
    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;
}