#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>

using namespace std;

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];
int 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) {
            int y = g[x][i];
            if (!viz[y]) {
                viz[y] = true;
                Q.push(y);
            }
        }
    }
}

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

        n = getInt();
        m = getInt();

        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();
            }
        }*/

        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);
            //fout << x << c << y << "\n";
            //rev[y][wh].push_back(x);
            g[x][wh] = 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<pair<int,int>> 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});
                }*/
            }
        }

        bool changes = true;

        while(changes)
        {
            changes = false;

            for (int i = 0; i < n; ++i)
            {
                if (!distinct[i])
                    continue;
                for (int j = i+1; j < n; ++j)
                {
                    if (!distinct[j])
                        continue;
                    if (same[i][j])
                    {
                        for (int c = 0; c < m; ++c)
                        {
                            int a = g[i][c];
                            int b = g[j][c];
                            if (a > b)
                                swap(a,b);

                            if (!same[a][b])
                            {
                                same[i][j] = false;
                                changes = true;
                                break;
                            }
                        }
                    }
                }
            }
        }

        /*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";
    }
}