#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using pii = pair<short, short>;
#define dbg(x) cerr<<#x": "<<(x)<<'\n'
#define dbg_v(x, n) {cerr<<#x"[]: ";for(long long _=0;_<n;++_)cerr<<(x)[_]<<' ';cerr<<'\n';}
#define all(v) v.begin(), v.end()
#define INF 2000000010
#define MOD 1000000007
#define ST_SIZE 1048600
#define QMAX 
#define NMAX 5210
#define LMAX 20010
#define SIGMA 15

int pos;
short nextState[NMAX][SIGMA];
bool sep[NMAX][NMAX];
bool final[NMAX];
char str[LMAX];
queue<pii> Q;
vector<pii> prevStates[NMAX][NMAX];

int getInt() {
	if(str[pos] == '\0') return -1;
	
	int x;
	
	for(x = 0; '0' <= str[pos] && str[pos] <= '9'; ++pos) x = x * 10 + str[pos] - '0';
	return x;
}

int main()
{
	freopen("robo.in", "r", stdin);
	freopen("robo.out", "w", stdout);
	ios_base::sync_with_stdio(false);
	
	int i, j, t, n, m, x, s1, s2, ans, minv, x1, x2, c;
	char act;
	
	for(cin >> t; t; --t) {
		memset(final, 0, sizeof final);
		
		cin >> n >> m;
		cin >> str;
		
		for(pos = 0; (x = getInt()) != -1; ) final[x] = true;
		
		while(cin >> s1 >> act >> s2)
			nextState[s1][act - 'a'] = s2;
		
		for(i = 0; i < n; ++i)
			for(j = i + 1; j < n; ++j)
				for(c = 0; c < m; ++c) {
					s1 = nextState[i][c];
					s2 = nextState[j][c];
					
					if(s1 > s2) swap(s1, s2);
					if(s1 != s2) prevStates[s1][s2].emplace_back(i, j);
				}
		
		for(i = 0; i < n; ++i)
			for(j = i + 1; j < n; ++j)
				if(final[i] != final[j])
					sep[i][j] = 1, Q.emplace(i, j);
				else
					sep[i][j] = 0;
		
		for(; !Q.empty(); Q.pop()) {
			s1 = Q.front().first;
			s2 = Q.front().second;
			
			//cerr << s1 << ' ' << s2 << '\n';
			
			for(auto p : prevStates[s1][s2]) {
				x1 = p.first;
				x2 = p.second;
				
				if(x1 != -1 && x2 != -1 && !sep[x1][x2]) {
					sep[x1][x2] = true;
					Q.emplace(x1, x2);
				}
			}
		}
		
		for(i = 0; i < n; ++i)
			for(j = i + 1; j < n; ++j)
				sep[j][i] = sep[i][j];
		
		ans = 0;
		for(i = 0; i < n; ++i) {
			for(minv = i, j = 0; j < n; ++j)
				if(!sep[i][j])
					minv = min(minv, j);
			
			if(minv == i) ++ans;
		}
		
		cout << ans << '\n';
		
		for(i = 0; i < n; ++i)
			for(j = 0; j < n; ++j)
				prevStates[i][j].clear();
	}
	
	return 0;
}