#include <fstream>
//#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

ifstream cin("robo.in");
ofstream cout("robo.out");

const int MAXN = 5200;
const int MAXM = 10;
const int BASE = 67;
const int MOD = 666013;

int number[MAXN];
int edge[MAXN][MAXM];
pair<pair<int, int>, int> v[MAXN];

int main() {
    int tests;
    cin >> tests;
    for (int test = 1; test <= tests; test++) {
        int n, m;
        string s;
        cin >> n >> m >> s;
        for (int i = 0; i < n; i++)
            number[i] = 0;
        for (int i = 0, j; i < s.size(); i = j) {
            j = i;
            int x = 0;
            while (j < s.size() && isdigit(s[j])) {
                x = x * 10 + s[j] - '0';
                j++;
            }
            number[x] = 1;
            while (j < s.size() && !isdigit(s[j]))
                j++;
        }
        for (int i = 1; i <= m * n; i++) {
            int a, b;
            char c;
            cin >> a >> c >> b;
            edge[a][c - 'a'] = b;
        }
        int numbers = 0;
        while (1) {
            numbers = 0;
            for (int i = 0; i < n; i++) {
                numbers = max(numbers, number[i]);
                v[i].second = i;
                v[i].first.second = number[i];
                v[i].first.first = 0;
                for (int j = 0; j < m; j++)
                    v[i].first.first = (v[i].first.first * BASE + number[edge[i][j]]) % MOD;
            }
            sort(v, v + n);
            int newNumber = -1;
            for (int i = 0; i < n; i++) {
                if (!i || v[i].first != v[i - 1].first)
                    newNumber++;
                number[v[i].second] = newNumber;
            }
            if (numbers == newNumber)
                break;
        }
        cout << numbers + 1 << "\n";
    }
    return 0;
}