#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;
for(i=0;i<n;i=i+1){
ans[i]=0;
scanf("%c %lld",&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+IHZpOwp0eXBlZGVmIHBhaXI8aW50LGludD4gaWk7CnR5cGVkZWYgdmVjdG9yPGlpPiB2aWk7CiAKdHlwZWRlZiB1bnNpZ25lZCBpbnQgdWk7CnR5cGVkZWYgdW5zaWduZWQgbG9uZyBsb25nIGxsdTsKdHlwZWRlZiB1bnNpZ25lZCBsb25nIGx1Owp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKI2RlZmluZSBNQVhfTiAxMDAwMTAKIAovLy0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KIAppbnQgbWFpbigpewoJbGwgdGVzdCxuLGwsYW5zWzEwMDAwMV0saixrOwoJbGwgaTsKCWxsIGxlbixjbXBuWzEwMDAwMV0sYlsxMDAwMDFdOwoJY2hhciBzWzEwMDAwMV0sY21wWzEwMDAwMV07CglsbCB0cFsxMDAwMTBdOwoJY2hhciB0YVsxMDAwMTBdOwoJYml0c2V0PDEwMDAwMT4gbGVhZixub2RlczsKIAoJc2NhbmYoIiVsbGQiLCZ0ZXN0KTsKCXdoaWxlKHRlc3QtLSl7CgkJLy9JbnB1dAoJCWxlYWYuc2V0KCk7CgkJbm9kZXMuc2V0KCk7CgkJc2NhbmYoIiVsbGQgJWxsZCIsJm4sJmwpOwoJCXNjYW5mKCIlcyIscyk7CgkJZm9yIChpPTA7IGk8bC8yOyBpKyspCgkJICAgIHN3YXAoc1tpXSwgc1tsLWktMV0pOwoJCS8vY291dDw8IlJldmVyc2UgU3RyaW5nOiI8PHM8PGVuZGw7CgkJLy9jb3V0PDxuPDxsOwoJCQoJCQoJCWZvcihpPTA7aTxuO2k9aSsxKXsKCQkJYW5zW2ldPTA7CgkJCXNjYW5mKCIlYyAlbGxkIiwmdGFbaV0sJnRwW2ldKTsKCQkJLy9jaW4+PnRhW2ldPj50cFtpXTsKCQkJdHBbaV0tLTsKCQkJLy9jb3V0PDx0W2ldLnA8PGVuZGw7CgkJCWlmKHRwW2ldPj0wKQoJCQkJbGVhZi5yZXNldCh0cFtpXSk7CgkJCS8vY291dDw8aTw8ZW5kbDsKCQl9CiAKCQkvL0RGUyBQYXRoCgkJZm9yKGk9MDtpPG47aSsrKXsKCQkJaWYobGVhZltpXSl7CgkJCQkvL2NvdXQ8PCJMZWFmICI8PGk8PGVuZGw7CgkJCQlsZW49MCxqPWk7CgkJCQl3aGlsZShqIT0tMSl7CgkJCQljbXBuW2xlbl09ajsKCQkJCWNtcFtsZW4rK109dGFbal07CgkJCQlqPXRwW2pdOwoJCQkJfQoJCQkJLy9jb3V0PDwiREZTIFN0cmluZyAiPDxjbXA8PGVuZGw7CgkJCQkvL1ByZS1Qcm9jZXNzCgkJCQkJbGwgaT0wLGo9LTE7CgkJCQkJYlswXT0tMTsKCQkJCQl3aGlsZShpPGwpewoJCQkJCQl3aGlsZShqPj0wICYmIHNbaV0hPXNbal0pIGo9YltqXTsKCQkJCQkJaSsrO2orKztiW2ldPWo7CgkJCQkJfQoJCQkJCS8vU2VhcmNoCgkJCQkJaT0wLGo9MDsKCQkJCQl3aGlsZShpPGxlbil7CgkJCQkJCXdoaWxlIChqPj0wICYmIGNtcFtpXSE9c1tqXSkgaj1iW2pdOwoJCQkJCQlpKys7aisrOwoJCQkJCQlpZiAoaj09bCAmJiBub2Rlc1tjbXBuW2ktal1dKXsKCQkJCQkJCWZvcihrPWxlbi0xO2s+PWktajtrLS0pCgkJCQkJCQlhbnNbY21wbltrXV0rPTE7CgkJCQkJCQlub2Rlc1tjbXBuW2ktal1dPWZhbHNlOwoJCQkJCQkJaj1iW2pdOwoJCQkJCQl9CgkJCQkJfQoJCQkJCgkJCX0KCQl9CiAKCQkvL0Fuc3dlcgoJCWZvcihpPTA7aTxuO2krKykKCQkJcHJpbnRmKCIlbGxkICIsYW5zW2ldKTsKCQlwcmludGYoIlxuIik7Cgl9CglyZXR1cm4gMDsKfQ==