#include <cstring>
#include <memory>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <sstream>
#include <limits>
#include <cctype>
#include <string>
#include <iterator>
#include <algorithm>
#include <bitset>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <functional>
#include <utility>
#include <fstream>
#include <tuple>
#include <list>

using namespace std;

#define DEBUG(x)\
    cerr << #x" = " << x << endl;

ifstream fin("robo.in");
ofstream fout("robo.out");

#define MAX_STATES 5201
#define MAX_ACTIONS 11

template<class T>
ostream& operator << (ostream& out, const vector<T>& v) {
    for (const auto& e : v) {
        out << e << ' ';
    }
    return out;
}

int no_states, no_act;
int trans[MAX_STATES][MAX_ACTIONS];
int grp[MAX_STATES][MAX_ACTIONS];

unordered_set<int> acc_states;
unordered_map<int, int> st_grp;
unordered_set<int> actions;

void read() {
    fin >> no_states >> no_act;

    //cout << no_states << ' ' << no_act << '\n';

    string line;
    getline(fin, line);
    getline(fin, line);
    stringstream ss(line);
    while (ss) {
        int acc_state;
        ss >> acc_state;
        acc_states.insert(acc_state);
    }

    for (int i = 0; i < 2 * no_states; ++i) {
        int s, next_s;
        char sym;

        fin >> s >> sym >> next_s;

        int sym_int = sym - 'a';
        actions.insert(sym_int);
        trans[s][sym_int] = next_s;
    }

    //for (int i = 0; i < no_states; ++i) {
        //for (int j = 0; j < no_act; ++j) {
            //cout << trans[i][j] << ' ';
        //}
        //cout << '\n';
    //}
}

vector<vector<int>> init() {
    vector<int> grp0, grp1;

    for (int i = 0; i < no_states; ++i) {
        if (acc_states.find(i) != acc_states.end()) {
            grp0.push_back(i);
            st_grp[i] = 0;
        } else {
            grp1.push_back(i);
            st_grp[i] = 1;
        }
    }

    vector<vector<int>> sol;
    sol.push_back(grp0);
    sol.push_back(grp1);

    return sol;
}

int solve() {
    vector<vector<int>> old_grps = init();
    vector<vector<int>> new_grps;
    unordered_map<int, int> new_st_grp;
    //DEBUG(old_grps);

    int has_changed = 1;
    while (has_changed) {
        has_changed = 0;

        for (auto g : old_grps) {
            for (auto state : g) {
                for (auto act : actions) {
                    int next_s = trans[state][act];
                    int next_s_grp = st_grp[next_s];

                    grp[state][act] = next_s_grp;
                }
            }
        }

        //for (int i = 0; i < no_states; ++i) {
            //for (int j = 0; j < no_act; ++j) {
                //cout << grp[i][j] << ' ';
            //}
            //cout << '\n';
        //}

        unordered_set<int> choosen_states;
        int grp_no = -1;

        for (int i = 0; i < no_states; ++i) {
            if (choosen_states.find(i) != choosen_states.end())
                continue;

            vector<int> new_grp;
            new_grp.push_back(i);

            grp_no++;
            new_st_grp.insert(make_pair(i, grp_no));
            choosen_states.insert(i);

            for (int j  = i + 1; j < no_states; ++j) {
                int diff = 0;

                for (int k = 0; k < no_act; ++k) {
                    if (grp[i][k] != grp[j][k]) {
                        diff = 1;
                        break;
                    }
                }

                if (!diff) {
                    new_st_grp.insert(make_pair(j, grp_no));
                    new_grp.push_back(j);
                    choosen_states.insert(j);
                }
            }
            //cout << new_grp << '\n';
            new_grps.push_back(new_grp);
        }

        if (new_grps == old_grps) {
            has_changed = 1;
            old_grps.clear();

            for (int i = 0; i < new_grps.size(); ++i) {
                //cout << new_grps[i];
                old_grps.push_back(new_grps[i]);
                st_grp = new_st_grp;
                new_st_grp.clear();
            }
            new_grps.clear();
        }
    }

    return new_grps.size();
}

int main() {
    int T;

    fin >> T;
    for (int i = 0; i < T; ++i) {
        read();
        fout << solve() << '\n';
    }

    fin.close();
    fout.close();
    return 0;
}