/*************************************************************\
~*********************ENJOY THE SILENCE***********************~
\*************************************************************/

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

/*******************Debugging defines*************************/

#define ok_dump() cerr<<"OK\n"
#define var_dump(x) cerr<<#x": "<<x<<'\n'
#define arr_dump(x, n) {cerr<<#x"[]: ";\
	for(int _=0;_<n;++_) cerr<<x[_]<<" ";cerr<<'\n';}

/*************************************************************/

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 5205;

struct DFA {
	

	int nodes, sigma;
	int T[MAXN][15];
	vector<int> Rev[MAXN][15];
	vector<int> Final;
	bitset<MAXN> IsFinal;
	bitset<MAXN> Eq[MAXN];

	void init(int nodes, int sigma) {
		this->nodes = nodes;
		this->sigma = sigma;

		for(int i = 1; i <= nodes; ++i) {
			memset(T[i], 0, sizeof(T[i]));
			Eq[i].set();
			for(int j = 0; j < sigma; ++j)
				Rev[i][j].clear();
		}
		Final.clear();
		IsFinal.reset();
	}

	void addEdge(int a, char c, int b) {
		T[a][c - 'a'] = b;
		Rev[b][c - 'a'].push_back(a);
	}

	void minimize() {
		queue<pair<int, int>> Q;

		for(auto final : Final)
			for(int i = 1; i <= nodes; ++i) {
				if(!IsFinal[i]) {
					Eq[final][i] = Eq[i][final] = 0;
					Q.emplace(final, i);
				}
			}

		while(!Q.empty()) {
			auto p = Q.front();
			Q.pop();

			int a = p.first,
				b = p.second;

			for(int i = 0; i < sigma; ++i) {
				for(auto x : Rev[a][i])
					for(auto y : Rev[b][i]) {
						if(Eq[x][y]) {
							Eq[x][y] = Eq[y][x] = 0;
							Q.emplace(x, y);
						}
					}
			}
		}
	}

	int countClasses() {
		
		bitset<MAXN> Class;
		Class.reset();

		int ret = 0;
		for(int i = 1; i <= nodes; ++i) {
			if(Class[i] == 1) continue;

			++ret;
			for(int j = 0; j <= nodes; ++j) {
				if(Eq[i][j]) 
					Class[j] = 1;
			}
		}

		return ret;
	}
};
DFA A;

int main() {	
//	assert(freopen("input.txt", "r", stdin));
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	ifstream fin("robo.in");
	ofstream fout("robo.out");

	int t;
	fin >> t;

	while(t--) {
		int a, b, n, sigma;
		char c;
		fin >> n >> sigma;
		A.init(n, sigma);
		fin.get();


		string s;
		getline(fin, s);
		stringstream ssin(s);
		while(ssin >> a) {
			A.Final.push_back(a + 1);
			A.IsFinal[a + 1] = 1;
		}

		int newn, newm;

		int cnt = 0;

		for(int i = 0; i < n * sigma; ++i) {
			fin >> a >> c >> b;
			A.addEdge(a + 1, c, b + 1);
		}

		

		A.minimize();

/*
		cerr << "Added " << cnt << " edges.\n";
		arr_dump(A.Final, A.Final.size());

		for(int i = 0; i < A.nodes; ++i)
			arr_dump(A.Eq[i], A.nodes + 1);
*/		


		fout << A.countClasses() << '\n';
		n = newn, sigma = newm;
	}
	return 0;
}

/*************************************************************\
~*********************ENJOY THE SILENCE***********************~
\*************************************************************/