#include <cassert>
#include <fstream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <bitset>
#include <ctime>
#include <set>
#include <cmath>
#include <iomanip>
#include <map>
#include <stack>
#include <vector>
#include <bitset>
#include <cassert>

#include <fstream>

using namespace std;

#define FOR(i, a, n) for (int i = a; i <= n; ++i)
#define ROF(i, n, a) for (int i = n; i >= a; i--)
#define FIT(i, v) for (auto &i : v)
#define pb push_back
#define mp make_pair
#define mt make_touple
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
typedef long long ll;
typedef pair<int,int> pii;
const int mod = 2000003;
ll powmod(ll a, ll b) {ll res=1; a %= mod; assert(b >= 0); for(; b; b >>= 1) {if (b & 1) res = res * a % mod; a = a * a % mod;} return res;}

const int N = 6000;

ifstream fin("robo.in");
ofstream fout("robo.out");
int p, len;
int n, m;
bool dest[N], viz[N];
vector<int> rev[N][10], g[N][10];
bool same[N][N];
string s;

void readLine() {
    do {
        getline(fin, s);
        p = 0;
        len = s.length();
    } while(len == 0);
}

bool isDigit(char c) {
    return ('0' <= c && c <= '9');
}

int getInt() {
    while (p < len && !isDigit(s[p]))
        ++p;
    if (p == len) {
        return -1;
    }
    int x = 0;
    while (p < len && isDigit(s[p])) {
        x = x * 10 + (s[p] - '0');
        ++p;
    }
    return x;
}

char getChar() {
    while (p < len && s[p] == ' ')
        ++p;
    char c = s[p];
    ++p;
    return c;
}

int get(map<char,int> &M, char c) {
    if (M.find(c) == M.end()) {
        int x = M.size();
        M[c] = x;
        return x;
    } else {
        return M[c];
    }
}

void bfs(int x) {
    for (int i = 0; i < n; ++i) {
        viz[i] = false;
    }
    viz[x] = true;
    queue<int> Q;
    Q.push(x);

    while(!Q.empty()) {
        int x = Q.front();
        Q.pop();

        for (int i = 0; i < m; ++i) {
            for (auto &y : g[x][i]) {
                if (!viz[y]) {
                    viz[y] = true;
                    Q.push(y);
                }
            }
        }
    }
}

int main() {
    readLine();
    int t = getInt();
    assert (t <= 10);
    while (t--) {
        readLine();

        n = getInt();
        assert(n <= 5200);
        m = getInt();
        assert (m <= 10);

        for (int i = 0; i < n; ++i) {
            dest[i] = false;
        }

        readLine();
        int x = getInt();
        do {
            dest[x] = true;
            x = getInt();
        } while(x != -1);

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                rev[i][j].clear();
                g[i][j].clear();
            }
        }

        map<char, int> M;
        for (int i = 1; i <= n*m; ++i) {
            readLine();
            int x = getInt();
            char c = getChar();
            int y = getInt();
            int wh = get(M, c);
            assert (0 <= x && x < n);
            assert (0 <= y && y < n);
            assert ('a' <= c && c <= 'z');
            //fout << x << c << y << "\n";
            rev[y][wh].push_back(x);
            g[x][wh].push_back(y);
        }

        /*for (int i = 0; i < n; ++i) {
            for (int c = 0; c < m; ++c) {
                assert(g[i][c].size() == 1);
            }
        }*/
        bfs(0);
        vector<bool> distinct(n);
        for (int i = 0; i < n; ++i) {
            distinct[i] = viz[i];
        }

        queue<pii> Q;
        for (int i = 0; i < n; ++i) {
            if (!distinct[i])
                continue;
            for (int j = i; j < n; ++j) {
                if (!distinct[j])
                    continue;
                same[i][j] = (dest[i] == dest[j]);
                if (!same[i][j]) {
                    Q.push({i, j});
                }
            }
        }

        while(!Q.empty()) {
            int x = Q.front().first;
            int y = Q.front().second;
            Q.pop();

            for (int c = 0; c < m; ++c) {
                for (auto xx : rev[x][c]) {
                    for (auto yy : rev[y][c]) {
                        if (!distinct[xx]) {
                            continue;
                        }
                        if (!distinct[yy]) {
                            continue;
                        }
                        if (xx > yy) {
                            int tmp = xx;
                            xx = yy;
                            yy = tmp;
                        }
                        if (same[xx][yy]) {
                            same[xx][yy] = false;
                            Q.push({xx, yy});
                        }
                    }
                }
            }
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (distinct[i]) {
                ++ans;
                for (int j = i+1; j < n; ++j) {
                    if (same[i][j]) {
                        distinct[j] = false;
                    }
                }
            }
        }

        fout << ans << "\n";
    }
}