#include <iostream>
#include <vector>
#include <stack>
#include <bitset>
#include <fstream>
#include <string.h>
#include <list>
#include <math.h>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef unsigned int ui;
typedef unsigned long long llu;
typedef unsigned long lu;
typedef long long ll;
#define MAX_N 100010
//----------------------------------------------------
int main(){
ll test,n,l,ans[100001],j,k;
ll i;
ll len,cmpn[100001],b[100001];
char s[100001],cmp[100001];
ll tp[100010];
char ta[100010];
bitset<100001> leaf,nodes;
scanf("%lld",&test);
while(test--){
//Input
leaf.set();
nodes.set();
scanf("%lld %lld",&n,&l);
scanf("%s",s);
for (i=0; i<l/2; i++)
swap(s[i], s[l-i-1]);
//cout<<"Reverse String:"<<s<<endl;
//cout<<n<<l;
char ccc;//line to read the newline
scanf("%c", &ccc);
for(i=0;i<n;i=i+1){
ans[i]=0;
scanf("%c %lld\n", &ta[i],&tp[i]);
//cin>>ta[i]>>tp[i];
tp[i]--;
//cout<<t[i].p<<endl;
if(tp[i]>=0)
leaf.reset(tp[i]);
//cout<<i<<endl;
}
//DFS Path
for(i=0;i<n;i++){
if(leaf[i]){
//cout<<"Leaf "<<i<<endl;
len=0,j=i;
while(j!=-1){
cmpn[len]=j;
cmp[len++]=ta[j];
j=tp[j];
}
//cout<<"DFS String "<<cmp<<endl;
//Pre-Process
ll i=0,j=-1;
b[0]=-1;
while(i<l){
while(j>=0 && s[i]!=s[j]) j=b[j];
i++;j++;b[i]=j;
}
//Search
i=0,j=0;
while(i<len){
while (j>=0 && cmp[i]!=s[j]) j=b[j];
i++;j++;
if (j==l && nodes[cmpn[i-j]]){
for(k=len-1;k>=i-j;k--)
ans[cmpn[k]]+=1;
nodes[cmpn[i-j]]=false;
j=b[j];
}
}
}
}
//Answer
for(i=0;i<n;i++)
printf("%lld ",ans[i]);
printf("\n");
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8c3RhY2s+CiNpbmNsdWRlIDxiaXRzZXQ+CiNpbmNsdWRlIDxmc3RyZWFtPgojaW5jbHVkZSA8c3RyaW5nLmg+CiNpbmNsdWRlIDxsaXN0PgojaW5jbHVkZSA8bWF0aC5oPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKIAp0eXBlZGVmIHZlY3RvcjxpbnQ+IHZpOwp0eXBlZGVmIHBhaXI8aW50LGludD4gaWk7CnR5cGVkZWYgdmVjdG9yPGlpPiB2aWk7CiAKdHlwZWRlZiB1bnNpZ25lZCBpbnQgdWk7CnR5cGVkZWYgdW5zaWduZWQgbG9uZyBsb25nIGxsdTsKdHlwZWRlZiB1bnNpZ25lZCBsb25nIGx1Owp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKI2RlZmluZSBNQVhfTiAxMDAwMTAKIAovLy0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KIAppbnQgbWFpbigpewoJbGwgdGVzdCxuLGwsYW5zWzEwMDAwMV0saixrOwoJbGwgaTsKCWxsIGxlbixjbXBuWzEwMDAwMV0sYlsxMDAwMDFdOwoJY2hhciBzWzEwMDAwMV0sY21wWzEwMDAwMV07CglsbCB0cFsxMDAwMTBdOwoJY2hhciB0YVsxMDAwMTBdOwoJYml0c2V0PDEwMDAwMT4gbGVhZixub2RlczsKIAoJc2NhbmYoIiVsbGQiLCZ0ZXN0KTsKCXdoaWxlKHRlc3QtLSl7CgkJLy9JbnB1dAoJCWxlYWYuc2V0KCk7CgkJbm9kZXMuc2V0KCk7CgkJc2NhbmYoIiVsbGQgJWxsZCIsJm4sJmwpOwoJCXNjYW5mKCIlcyIscyk7CgkJZm9yIChpPTA7IGk8bC8yOyBpKyspCgkJICAgIHN3YXAoc1tpXSwgc1tsLWktMV0pOwoJCS8vY291dDw8IlJldmVyc2UgU3RyaW5nOiI8PHM8PGVuZGw7CgkJLy9jb3V0PDxuPDxsOwogCgkJY2hhciBjY2M7Ly9saW5lIHRvIHJlYWQgdGhlIG5ld2xpbmUKCQlzY2FuZigiJWMiLCAmY2NjKTsKIAoJCWZvcihpPTA7aTxuO2k9aSsxKXsKCQkJYW5zW2ldPTA7CgkJCXNjYW5mKCIlYyAlbGxkXG4iLCAmdGFbaV0sJnRwW2ldKTsKCQkJLy9jaW4+PnRhW2ldPj50cFtpXTsKCQkJdHBbaV0tLTsKCQkJLy9jb3V0PDx0W2ldLnA8PGVuZGw7CgkJCWlmKHRwW2ldPj0wKQoJCQkJbGVhZi5yZXNldCh0cFtpXSk7CgkJCS8vY291dDw8aTw8ZW5kbDsKCQl9CgkJLy9ERlMgUGF0aAoJCWZvcihpPTA7aTxuO2krKyl7CgkJCWlmKGxlYWZbaV0pewoJCQkJLy9jb3V0PDwiTGVhZiAiPDxpPDxlbmRsOwoJCQkJbGVuPTAsaj1pOwoJCQkJd2hpbGUoaiE9LTEpewoJCQkJY21wbltsZW5dPWo7CgkJCQljbXBbbGVuKytdPXRhW2pdOwoJCQkJaj10cFtqXTsKCQkJCX0KCQkJCS8vY291dDw8IkRGUyBTdHJpbmcgIjw8Y21wPDxlbmRsOwoJCQkJLy9QcmUtUHJvY2VzcwoJCQkJCWxsIGk9MCxqPS0xOwoJCQkJCWJbMF09LTE7CgkJCQkJd2hpbGUoaTxsKXsKCQkJCQkJd2hpbGUoaj49MCAmJiBzW2ldIT1zW2pdKSBqPWJbal07CgkJCQkJCWkrKztqKys7YltpXT1qOwoJCQkJCX0KCQkJCQkvL1NlYXJjaAoJCQkJCWk9MCxqPTA7CgkJCQkJd2hpbGUoaTxsZW4pewoJCQkJCQl3aGlsZSAoaj49MCAmJiBjbXBbaV0hPXNbal0pIGo9YltqXTsKCQkJCQkJaSsrO2orKzsKCQkJCQkJaWYgKGo9PWwgJiYgbm9kZXNbY21wbltpLWpdXSl7CgkJCQkJCQlmb3Ioaz1sZW4tMTtrPj1pLWo7ay0tKQoJCQkJCQkJYW5zW2NtcG5ba11dKz0xOwoJCQkJCQkJbm9kZXNbY21wbltpLWpdXT1mYWxzZTsKCQkJCQkJCWo9YltqXTsKCQkJCQkJfQoJCQkJCX0KIAoJCQl9CgkJfQogCgkJLy9BbnN3ZXIKCQlmb3IoaT0wO2k8bjtpKyspCgkJCXByaW50ZigiJWxsZCAiLGFuc1tpXSk7CgkJcHJpbnRmKCJcbiIpOwoJfQoJcmV0dXJuIDA7Cn0=