#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,l,ans[100001],j,k;
ll i;
ll len,cmpn[100001],b[100001];
char s[100001],cmp[100001];
ll n,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]);
for(i=0;i<n;i=i+1){
//scanf("%c %lld",&ta[i],&tp[i]);
cin>>ta[i]>>tp[i];
tp[i]--;
ans[i]=0;
if(tp[i]>=0)
leaf.reset(tp[i]);
}
//DFS Path
for(i=0;i<n;i++){
if(leaf[i]){
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+IHZpOwp0eXBlZGVmIHBhaXI8aW50LGludD4gaWk7CnR5cGVkZWYgdmVjdG9yPGlpPiB2aWk7CiAKdHlwZWRlZiB1bnNpZ25lZCBpbnQgdWk7CnR5cGVkZWYgdW5zaWduZWQgbG9uZyBsb25nIGxsdTsKdHlwZWRlZiB1bnNpZ25lZCBsb25nIGx1Owp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKI2RlZmluZSBNQVhfTiAxMDAwMTAKIAovLy0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KCmludCBtYWluKCl7CglsbCB0ZXN0LGwsYW5zWzEwMDAwMV0saixrOwoJbGwgaTsKCWxsIGxlbixjbXBuWzEwMDAwMV0sYlsxMDAwMDFdOwoJY2hhciBzWzEwMDAwMV0sY21wWzEwMDAwMV07CglsbCBuLHRwWzEwMDAxMF07CgljaGFyIHRhWzEwMDAxMF07CgliaXRzZXQ8MTAwMDAxPiBsZWFmLG5vZGVzOwogCglzY2FuZigiJWxsZCIsJnRlc3QpOwoJd2hpbGUodGVzdC0tKXsKCQkvL0lucHV0CgkJbGVhZi5zZXQoKTsKCQlub2Rlcy5zZXQoKTsKCQlzY2FuZigiJWxsZCAlbGxkIiwmbiwmbCk7CgkJc2NhbmYoIiVzIixzKTsKCQlmb3IgKGk9MDsgaTxsLzI7IGkrKykKCQkgICAgc3dhcChzW2ldLCBzW2wtaS0xXSk7CgkJIAoJCWZvcihpPTA7aTxuO2k9aSsxKXsKCQkJLy9zY2FuZigiJWMgJWxsZCIsJnRhW2ldLCZ0cFtpXSk7CgkJCWNpbj4+dGFbaV0+PnRwW2ldOwoJCQl0cFtpXS0tOwoJCQkKCQkJYW5zW2ldPTA7CgkJCWlmKHRwW2ldPj0wKQoJCQkJbGVhZi5yZXNldCh0cFtpXSk7CQoJCX0KIAoJCS8vREZTIFBhdGgKCQlmb3IoaT0wO2k8bjtpKyspewoJCQlpZihsZWFmW2ldKXsKCQkJCWxlbj0wLGo9aTsKCQkJCXdoaWxlKGohPS0xKXsKCQkJCWNtcG5bbGVuXT1qOwoJCQkJY21wW2xlbisrXT10YVtqXTsKCQkJCWo9dHBbal07CgkJCQl9CgkJCQkvL2NvdXQ8PCJERlMgU3RyaW5nICI8PGNtcDw8ZW5kbDsKCQkJCS8vUHJlLVByb2Nlc3MKCQkJCQlsbCBpPTAsaj0tMTsKCQkJCQliWzBdPS0xOwoJCQkJCXdoaWxlKGk8bCl7CgkJCQkJCXdoaWxlKGo+PTAgJiYgc1tpXSE9c1tqXSkgaj1iW2pdOwoJCQkJCQlpKys7aisrO2JbaV09ajsKCQkJCQl9CgkJCQkJLy9TZWFyY2gKCQkJCQlpPTAsaj0wOwoJCQkJCXdoaWxlKGk8bGVuKXsKCQkJCQkJd2hpbGUgKGo+PTAgJiYgY21wW2ldIT1zW2pdKSBqPWJbal07CgkJCQkJCWkrKztqKys7CgkJCQkJCWlmIChqPT1sICYmIG5vZGVzW2NtcG5baS1qXV0pewoJCQkJCQkJZm9yKGs9bGVuLTE7az49aS1qO2stLSkKCQkJCQkJCWFuc1tjbXBuW2tdXSs9MTsKCQkJCQkJCW5vZGVzW2NtcG5baS1qXV09ZmFsc2U7CgkJCQkJCQlqPWJbal07CgkJCQkJCX0KCQkJCQl9CgkJCX0KCQl9CiAKCQkvL0Fuc3dlcgoJCWZvcihpPTA7aTxuO2krKykKCQkJcHJpbnRmKCIlbGxkICIsYW5zW2ldKTsKCQlwcmludGYoIlxuIik7Cgl9CglyZXR1cm4gMDsKfQog