#include <fstream>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>

using namespace std;

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

const int nmax = 5200;
const int nrac = 10;
const int base = nmax + 1;
const int mod1 = 666013;
const int mod2 = 666019;

int n, nra;
int tip[nmax + 1];
int u[nmax + 1][nrac + 1];

string aux;
stringstream _aux;

struct Hash {
    int ind, x, y;

    Hash() {}
    Hash (int _ind, int _x, int _y) {
        ind = _ind, x = _x, y = _y;
    }

    inline Hash operator + (const int &a) const {
        return Hash(ind, (1LL * x * base + a) % mod1, (1LL * y * base + a) % mod2);
    }
    inline bool operator == (const Hash &a) const {
        return (x == a.x && y == a.y);
    }
    inline bool operator < (const Hash &a) const {
        if (x != a.x) return (x < a.x);
        if (y != a.y) return (y < a.y);
        return (ind < a.ind);
    }
} v[nmax + 1];

void citire() {
    memset(tip, 0, sizeof(tip));

    fin >> n >> nra;

    while (fin.get() != '\n') {
    }

    getline(fin, aux, '\n');
    _aux << aux;
    int term;
    while (_aux >> term) {
        tip[ term ] = 1;
    }

    _aux.clear();

    for (int i = 0; i < n * nra; ++ i) {
        int x, y; char ch;
        fin >> x >> ch >> y;
        u[ x ][ch - 'a'] = y;
    }
}
int main() {
    int t;
    fin >> t;

    while (t --) {
        citire();

        int ind = 0;
        bool ok = 1;
        while (ok == 1) {
            for (int i = 0; i < n; ++ i) {
                v[ i ] = Hash(i, 0, 0);
                for (int j = 0; j < nra; ++ j) {
                    v[ i ] = v[ i ] + tip[ u[ i ][ j ] ];
                }
                //fout << i << " " << v[ i ].x << " " << v[ i ].y << "\n";
            }
            //fout << "\n";

            sort(v, v + n);

            int vechi = ind;
            ind = 0;
            for (int i = 0; i < n; ) {
                int j = i;
                while (j < n && v[ i ] == v[ j ]) {
                    tip[ v[ j ].ind ] = ind;
                    ++ j;
                }

                i = j;
                ++ ind;
            }

            ok = (vechi != ind);
        }

        //for (int i = 0; i < n; ++ i) fout << tip[ i ] << " "; fout << "\n";

        fout << ind << "\n";
    }

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