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



}