#include <bits/stdc++.h>
using namespace std;
const int NMAX = 5200;
const int SIGMAMAX = 10;
class Automaton {
public:
    Automaton(int n, int sigma, int q0 = 0): N(n), SIGMA(sigma), Q0(q0) {}
    void add_final_state(int node) {
        f.push_back(node);
    }
    void add_transition(int node1, char c, int node2) {
        trans[node1][c - 'a'] = node2;
    }
    int minimize() {
        memset(labels, 0, sizeof labels);
        for (auto it: f)
            labels[it] = 1;
        int labels_count_init = 0;
        while (1) {
            labels_count_init = 0;
            for (int i = 0; i < N; ++ i)
                labels_count_init = max(labels_count_init, labels[i]);
            for (int i = 0; i < N; ++ i) {
                sortable_table[i].first.first = 0;
                sortable_table[i].first.second = labels[i];
                sortable_table[i].second = i;

                for (int j = 0; j < SIGMA; ++ j) {
                    table[i][j] = labels[trans[i][j]];
                    sortable_table[i].first.first = (sortable_table[i].first.first * C + table[i][j]) % MOD;
                }
            }
            sort(sortable_table, sortable_table + N);
            int label = -1;
            for (int i = 0; i < N; ++ i) {
                if (!i || sortable_table[i].first != sortable_table[i - 1].first)
                    ++ label;
                labels[sortable_table[i].second] = label;
            }

            if (labels_count_init == label)
                break;
        }
        return labels_count_init + 1;
    }
private:
    const int N;
    const int SIGMA;
    const int Q0;
    vector <int> f;
    int trans[NMAX][SIGMAMAX];
    int table[NMAX][SIGMAMAX];
    int labels[NMAX];
    const int MOD = 666013;
    const int C = 67;
    pair <pair <int, int>, int> sortable_table[NMAX];
};
int main()
{
    ifstream cin("robo.in");
    ofstream cout("robo.out");
    int t;
    cin >> t;
    while (t --) {
        int n, sigma;
        cin >> n >> sigma; cin.ignore();
        Automaton aut(n, sigma);
        string str;
        getline(cin, str);
        stringstream ss(str + " ");
        int node;
        while (ss >> node)
            aut.add_final_state(node);
        int a, b;
        char c;
        for (int i = 0; i < n * sigma; ++ i) {
            cin >> a >> c >> b;
            aut.add_transition(a, c, b);
        }
        cout << aut.minimize() << '\n';
    }
    cin.close();
    cout.close();
    return 0;
}