#include <fstream>
//#include <iostream>
#include <cassert>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <sstream>
#include <utility>

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() {
        //Set labels according to accepting states
        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]);

            //Built auxiliary transition table
            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 the table
            sort(sortable_table, sortable_table + N);

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

    /*void print() {
        cout << "The finals are " << endl;
        for (auto it: f)
            cout << it << ' ';
        cout << endl;

        for (int i = 0; i < N; ++ i) {
            cout << "i = " << i << " -> ";
            for (int j = 0; j < SIGMA; ++ j)
                cout << trans[i][j] << ' ';
            cout << endl;
        }
    }*/
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 = 0;
    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);
        }

        //aut.print();
        cout << aut.minimize() << '\n';
    }

    cin.close();
    cout.close();
    return 0;
}