#include<bits/stdc++.h>
using namespace std;
#define cs const
#define re register
#define pb push_back
#define pii pair<int,int>
#define ll long long
#define y1 shinkle
#define fi first
#define se second
#define bg begin
namespace IO{

cs int RLEN=1<<22|1;
char ibuf[RLEN],*ib,*ob;
inline char gc(){
    (ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
    return (ib==ob)?EOF:*ib++;
}
inline int read(){
    char ch=gc();
    int res=0;bool f=1;
    while(!isdigit(ch))f^=ch=='-',ch=gc();
    while(isdigit(ch))res=(res*10)+(ch^48),ch=gc();
    return f?res:-res;
}
inline ll readll(){
    char ch=gc();
    ll res=0;bool f=1;
    while(!isdigit(ch))f^=ch=='-',ch=gc();
    while(isdigit(ch))res=(res*10)+(ch^48),ch=gc();
    return f?res:-res;
}
inline char readchar(){
	char ch=gc();
	while(isspace(ch))ch=gc();
	return ch;
}
inline int readstring(char *s){
	int top=0;char ch=gc();
	while(isspace(ch))ch=gc();
	while(!isspace(ch)&&ch!=EOF)s[++top]=ch,ch=gc();
	s[top+1]='\0';return top;
}

}
using IO::read;
using IO::readll;
using IO::readchar;
using IO::readstring;
template<typename tp>inline void chemx(tp &a,tp b){(a<b)?(a=b):0;}
template<typename tp>inline void chemn(tp &a,tp b){(a>b)?(a=b):0;}

cs int N=100005;

vector<int> f[N];
char s[N];
vector<int> e[N];
int n,dep[N],ans[N];
int cntr[N],cntb[N];
vector<int>t1[N],t2[N],t3[N],t4[N];
multiset<int>q1,q2;
void update(int u){
//	cout<<"Update "<<u<<'\n';
//	cout<<cntb[u]<<" "<<cntr[u]<<'\n';
//	for(int x:f[u])cout<<x<<" ";puts("");
	for(int i=0;i<f[u].size();i++){
		t1[i].pb(f[u][i]+cntb[u]+i);
		t2[i+cntb[u]].pb(f[u][i]+cntb[u]+i);
	//	cout<<i<<" "<<i+cntb[u]<<" "<<f[u][i]-i<<" "<<i+cntb[u]+cntr[u]<<'\n';
		t3[i+cntb[u]].pb(f[u][i]-i-cntb[u]);
		t4[i+cntb[u]+cntr[u]].pb(f[u][i]-i-cntb[u]);
	}
	f[u].resize(dep[u]+1);
	for(int i=0;i<=dep[u];i++){
		for(int x:t1[i]){
			q1.insert(x);
		}
		for(int x:t3[i]){
			q2.insert(x);
		}
	//	cout<<"Now "<<i<<'\n';
	//	for(int x:q1)cout<<x<<" ";puts("");
	//	for(int x:q2)cout<<x<<" ";puts("");
		int mn=1e9;
		if(q1.size())mn=min(mn,(*q1.begin())-i);
		if(q2.size())mn=min(mn,(*q2.begin())+i);
		f[u][i]=mn;
		for(int x:t2[i])q1.erase(q1.find(x));
		for(int x:t4[i])q2.erase(q2.find(x));
		t1[i].clear(),t2[i].clear(),t3[i].clear(),t4[i].clear();
	}q1.clear(),q2.clear();
	//for(int x:f[u])cout<<x<<" ";puts("");
}
void dp(int u){
	if(!e[u].size()){
		ans[u]=0;
		f[u].resize(2);
		f[u][0]=(s[u]!='0');
		f[u][1]=(s[u]!='1');
		dep[u]=1;
		return;
	}
	if(e[u].size()==1){
		dp(e[u][0]);
		swap(f[u],f[e[u][0]]);
		ans[u]=ans[e[u][0]];
		cntr[u]=cntr[e[u][0]];
		cntb[u]=cntb[e[u][0]];
		dep[u]=dep[e[u][0]]+1;
		if(s[u]=='0')cntr[u]++;
		else cntb[u]++;
		return;
	}
	int mn=1e9,mnp=0;
	for(int v:e[u]){
		dp(v);
		if(cntr[v]+cntb[v]){
			update(v);
		}
		if(mn>dep[v])mn=dep[v],mnp=v;
	}
	mn++;
	dep[u]=mn;
	swap(f[u],f[mnp]);
	f[u].resize(mn);
	for(int i=0;i<e[u].size();i++){
		int v=e[u][i];
		if(v==mnp)continue;
		for(int j=0;j<mn;j++)
		f[u][j]+=f[v][j];
	}
	f[u].pb(1e9);
	for(int i=mn;~i;i--){
		f[u][i]+=(s[u]=='1');
		if(i)chemn(f[u][i],f[u][i-1]+(s[u]=='0'));
	}
	ans[u]=1e9;
	for(int i=0;i<=mn;i++)chemn(ans[u],f[u][i]);
//	cout<<"now "<<u<<'\n';
//	for(int i=0;i<=mn;i++)cout<<f[u][i]<<" ";puts("");
}

void solve(){
	n=read();
	readstring(s);
	for(int i=2;i<=n;i++){
		int p=read();
		e[p].pb(i);
	}
	dp(1);
	for(int i=1;i<=n;i++){
		cout<<ans[i];
		if(i!=n)cout<<" ";
		else cout<<'\n';
	}
	for(int i=1;i<=n;i++)e[i].clear(),f[i].clear(),dep[i]=ans[i]=0,cntb[i]=cntr[i]=0;
}

int main(){
	#ifdef Stargazer
	freopen("1.in","r",stdin);
	//freopen("1.out","w",stdout);
	#endif
	int tt=clock();
	int T=read();
	while(T--)solve();
	//cerr<<clock()-tt<<'\n';
	return 0;
}