#include <cstdio>
#include <fstream>
#include <algorithm>
using namespace std;
ofstream g("robo.out");
int N, M;
int equiv[5205], nb;
int to[15][5205];
const int MOD = 1000000007;
const int BASE = 73;
char S[1005];
pair <pair <int, int>, int> V[5205];
void Read(){
    scanf("%d%d\n", &N, &M);
    fgets(S + 1, 1005, stdin);
    int val = 0, nb = 0;
    for(int i = 0; i < N; i++)
        equiv[i] = 0;
    for(int i = 1; S[i]; i++){
        if(S[i] >= '0' && S[i] <= '9')
            val = val * 10 + S[i] - '0';
        else{
            equiv[val] = 1;
            ++nb;
            val = 0;
        }
    }
    if(val != 0)
        equiv[val] = 1, nb++;
    for(int i = 1; i <= N * M; i++){
        int x, y;
        char c;
        scanf("%d %c%d", &x, &c, &y);
        to[c - 'a'][x] = y;
    }
}


void Solve(){
    int last = 0, cntClass = (nb == N ? 1 : 2);
    while(cntClass != last){
        last = cntClass;
        cntClass = 0;
        for(int i = 0; i < N; i++){
            cntClass = max(cntClass, equiv[i]);
            V[i] = make_pair(make_pair(0, equiv[i]), i);
            for(int j = 0; j < M; j++)
                V[i].first.first = (1LL * V[i].first.first * BASE + equiv[to[j][i]]) % MOD;
        }
        sort(V + 1, V + N + 1);
        int cnt = -1;
        for(int i = 1; i <= N; i++){
            if(i == 1 || V[i].first != V[i - 1].first)
                ++cnt;
            equiv[V[i].second] = cnt;
        }
    }
    g << cntClass + 1 << '\n';
}
int main()
{
    freopen("robo.in", "r", stdin);
    int T;
    scanf("%d", &T);
    while(T--){
        Read();
        Solve();
    }

    return 0;
}