#include<iostream>
#include<vector>
using namespace std;
int T,n,fa[100010],g[100010],h[100010],ans[100010];
char s[100010];
vector<int> e[100010],f[100010];
void dfs(int now)
{
	if(e[now].empty())
	{
		f[now].resize(1),f[now][0]=0;
		g[now]=1,h[now]=s[now]-'0';
		ans[now]=0;
		return;
	}
	if(e[now].size()==1)
	{
		int t=e[now][0];
		dfs(t);
		swap(f[now],f[t]);
		g[now]=g[t]+1;
		h[now]=h[t]+s[now]-'0';
		ans[now]=ans[t];
		return;
	}
	int S=1e9;
	for(int i=0;i<e[now].size();i++)
	{
		int t=e[now][i];
		dfs(t);
		S=min(S,int(f[t].size())+g[t]);
	}
	f[now].resize(S);
	for(int j=0;j<S;f[now][j++]=0);
	for(int i=0;i<e[now].size();i++)
	{
		int t=e[now][i];
		static pair<int,int> q1[100010],q2[100010];
		int l1=1,r1=0,l2=1,r2=0;
		for(int j=0;j<S;j++)
		{
			int v=1e9;
			if(j<f[t].size())
			{
				while(l1<=r1&&q1[r1].first>=f[t][j]+j)
				{
					r1--;
				}
				q1[++r1]={f[t][j]+j,j};
			}
			while(l1<=r1&&q1[l1].second<j-h[t])
			{
				l1++;
			}
			if(l1<=r1)
			{
				v=q1[l1].first-(j-h[t]);
			}
			if(j>h[t])
			{
				int J=j-h[t]-1;
				if(J<f[t].size())
				{
					while(l2<=r2&&q2[r2].first>=f[t][J]+J)
					{
						r2--;
					}
					q2[++r2]={f[t][J]-J,J};
				}
				while(l2<=r2&&q2[l2].second<j-g[t])
				{
					l2++;
				}
				if(l2<=r2)
				{
					v=min(v,q2[l2].first+(j-h[t]));
				}
			}
			f[now][j]+=v;
		}
	}
	ans[now]=1e9;
	for(int i=0;i<S;i++)
	{
		ans[now]=min(ans[now],f[now][i]);
	}
	g[now]=1,h[now]=s[now]-'0';
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>T;
	while(T--)
	{
		cin>>n>>s+1;
		for(int i=1;i<=n;i++)
		{
			e[i].clear();
		}
		for(int i=2;i<=n;i++)
		{
			cin>>fa[i];
			e[fa[i]].emplace_back(i);
		}
		dfs(1);
		for(int i=1;i<=n;i++)
		{
			cout<<ans[i];
			if(i<n)
			{
				cout<<" ";
			}
		}
		cout<<endl;
	}
	return 0;
}