/* 
	Prima problema faina de pe arhiva acm

	Ideea de baza a algoritmului e cam asa:
	
	- O sa ii atribuim un cod fiecarei stari (un hash)
	- Initial nu putem face diferenta decat intre starile finale si cele intermediare
	- Pe parcurs, o sa cream un nou cod pentru starea curenta in functie de codul ei actual si de codurie starilor vecine (in ordine) si o sa le normalizam
	- Daca nu s-a modificat niciun cod (nu am mai gasit vreo diferenta intre 2 stari care aveau la pasul anterior acelasi cod) atunci acestea sunt starile solutie 

*/
#include <bits/stdc++.h>
using namespace std;

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

const int DIM = 5205;
const int KMX = 10;

const int MOD1 = 100043;
const int MOD2 = 100049;

pair<pair<int, int>, int> hsh[DIM];
int val[DIM], nxt[DIM][KMX];

int main(void) {
	int t; in >> t;
	while (t--) {
		int n, m; in >> n >> m;
		for (int i = 1; i <= n; ++i)
			val[i] = 2;
		in.ignore();
		string str; getline(in, str);
		for (int p = 0; p < str.length(); ++p) {
			while (p < str.length() and !isdigit(str[p]))
				++p;
			if (p < str.length()) {
				int x = 0;
				while (p < str.length() and isdigit(str[p]))
					x = x * 10 + (str[p++] - '0');
				val[x + 1] = 1;
			}
		}
		for (int i = 1; i <= n * m; ++i) {
			int x, y; char ch; in >> x >> ch >> y;
			nxt[++x][ch - 'a'] = ++y;
		}
		int ant = 2, crt = 2;
		do {
			ant = crt; crt = 0;
			for (int i = 1; i <= n; ++i) {
				hsh[i] = { {val[i], val[i]}, i};
				for (int j = 0; j < m; ++j) 
					hsh[i].first = {(hsh[i].first.first * (n + 1) + val[nxt[i][j]]) % MOD1,
													(hsh[i].first.second * (n + 1) + val[nxt[i][j]]) % MOD2};
			}
			for (int i = 1, j = 1; i <= n; ) {
				while (j <= n and hsh[i].first == hsh[j].first)
					++j;
				++crt;
				while (i < j)
					val[hsh[i++].second] = crt;
			}
		} while (ant != crt);
		out << crt << "\n";
	}
	return 0;
}