#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 = 7919;

const int mod1 = 3391;

const int mod2 = 3931;



int n, nra;

int tip[nmax + 1];

int u[nmax + 1][nrac + 1];



string aux;

stringstream _aux;



struct Hash {

    int ind, ti, x, y;



    Hash() {}

    Hash (int _ind, int _ti, int _x, int _y) {

        ind = _ind, ti = _ti, x = _x, y = _y;

    }



    inline Hash operator + (const int &a) const {

        return Hash(ind, ti, (x * base + a) % mod1, (y * base + a) % mod2);

    }

    inline bool operator == (const Hash &a) const {

        return (x == a.x && y == a.y && ti == a.ti);

    }

    inline bool operator < (const Hash &a) const {

        if (x != a.x) return (x < a.x);

        if (y != a.y) return (y < a.y);

        if (ti != a.ti) return (ti < a.ti);

        return (ind < a.ind);

    }

} v[nmax + 1];



void citire() {

    memset(tip, 0, sizeof(tip));



    fin >> n >> nra; fin.ignore();



    getline(fin, aux);



    _aux.clear();

    _aux.str(aux + " ");

    int term;

    while (_aux >> term) {

        tip[ term ] = 1;

    }



    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 = 2;

        bool ok = 1;

        while (ok == 1) {

            for (int i = 0; i < n; ++ i) {

                v[ i ] = Hash(i, tip[ i ], 0, 0);

                for (int j = 0; j < nra; ++ j) {

                    v[ i ] = v[ i ] + tip[ u[ i ][ j ] ];

                }

                v[ i ] = v[ i ] + tip[ i ];

            }



            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);

        }



        fout << ind << "\n";

    }



    fin.close();

    fout.close();

    return 0;

}