#include<bits/stdc++.h>
#define psb push_back
using namespace std;
typedef long long LL;
inline int read(){
	char ch=getchar();
	while(!isdigit(ch) && ch!='-') ch=getchar();
	int x=0,ff=1; if(ch=='-') ff=-1,ch=getchar();
	while(isdigit(ch)) x=(x<<3) + (x<<1) + (ch^48),ch=getchar();
	return x*ff;
}
const int N=1e5+5,inf=1e9;
int n,fa[N],F[N],vd[N],zl[N],zr[N],b[N],b2[N],st[N],tp; vector<int> e[N],f[N]; char ch[N];
void dfs(int u){
	vd[u]=n; f[u].clear();
	for(int v:e[u]) dfs(v),vd[u]=min(vd[u],vd[v]);
	if(!e[u].size()) vd[u]=0, zl[u]=zr[u]=0, F[u]=0, f[u].psb(0);
	else if((int)e[u].size()==1){
		int v=e[u][0]; swap(f[u],f[v]);
		zl[u]=zl[v]; zr[u]=zr[v]; F[u]=F[v];
	} else{
		f[u].resize(vd[u]+1); F[u]=inf;
		for(int v:e[u]){
			int tt=-1;
			for(int i=1;i<=zl[v];i++) b[++tt]=f[v][0]+zl[v]-i+1;
			for(int x:f[v]) b[++tt]=x;
			for(int i=1;i<=zr[v];i++) b[++tt]=f[v].back()+i;
			for(int i=0;i<=tt;i++) b2[i]=b[i];
			tp=0;
			for(int i=tt;i>=0;i--){
				while(tp && b[st[tp]]+st[tp]>=b[i]+i) --tp;
				st[++tp]=i; int L=1,R=tp;
				while(L<R){
					int mid=(L+R)/2;
					if(st[mid]<=i+zl[v]) R=mid;
					else L=mid+1;
				} b2[i]=min(b2[i],b[st[R]]+st[R]-i);
			}
			tp=0;
			for(int i=0;i<=tt;i++){
				while(tp && b[st[tp]]-st[tp]>=b[i]-i) --tp;
				st[++tp]=i; int L=1,R=tp;
				while(L<R){
					int mid=(L+R)/2;
					if(st[mid]>=i-zr[v]) R=mid;
					else L=mid;
				} b2[i]=min(b2[i],b[st[R]]-st[R]+i);
			}
			for(int i=0;i<=vd[u];i++) f[u][i]=min(f[u][i]+b2[i],inf);
		} zl[u]=zr[u]=0; for(int i=0;i<=vd[u];i++) F[u]=min(F[u],f[u][i]);
	}
	++vd[u];
	if(ch[u]=='0') ++zr[u];
	else ++zl[u];
}
void vmain(){
	n=read(); scanf("%s",ch+1); for(int i=1;i<=n;i++) e[i].clear();
	for(int i=2;i<=n;i++) fa[i]=read(),e[fa[i]].psb(i);
	dfs(1);
	for(int i=1;i<=n;i++) printf("%d ",F[i]);
	puts("");
}
int main(){
	int T=read(); while(T--) vmain();	
	return 0;
}