#include<stdio.h>
#include<iostream>
#include<queue>
#include<algorithm>
#include<bitset>
#include<unordered_map>
#include<assert.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
const int maxn = 1e5+10,inf = 0x3f3f3f3f;

vector<int> G[maxn];
char s[maxn];

int sumB[maxn],sumR[maxn];  
int low[maxn];  //各棵子树的最小高度， dp[i][j]中j的取值范围为0~low[i]+(sumB+sumR)
int ansFatherID[maxn];  //如果不为自身，说明它在链上，被吞了，自己的dp值不会被调用；答案同父亲

void Dfs(int i){
    if(s[i]=='1') sumB[i]=1,sumR[i]=0;
    else sumB[i]=0,sumR[i]=1;
    ansFatherID[i]=i;

    while(G[i].size()==1){
        int j=G[i][0];
        ansFatherID[j]=i;

        //链压缩
        if(s[j]=='1') sumB[i]++;
        else sumR[i]++;
        G[i]=G[j];  
    }

    if(G[i].empty()) low[i]=0;
    else{
        int mn=inf;
        for(auto& y:G[i]){
            Dfs(y);
            mn=min(low[y]+(sumB[y]+sumR[y]),mn);
        }
        low[i]=mn;
    }
}

vector<int> dp[maxn];
int ans[maxn];
int tmp[maxn],sumSon[maxn];
deque<int> q;
void Dfs2(int i){
    if(G[i].empty()){
        dp[i]=vector<int>(sumB[i]+sumR[i] +1);
        dp[i][sumB[i]]=0;
        rep(j,sumB[i]+1,sumB[i]+sumR[i]) dp[i][j]=dp[i][j-1]+1;
        per(j,sumB[i]-1,0) dp[i][j]=dp[i][j+1]+1;

        ans[i]=0;
        return ;
    }

    for(auto& y:G[i]) Dfs2(y);

    rep(j,0,low[i]+sumB[i]+sumR[i]) tmp[j]=inf;
    rep(j,0,low[i]) sumSon[j]=0;

    for(auto& y:G[i]){
        rep(j,0,low[i]) sumSon[j]+=dp[y][j];
    }
    rep(j,0,low[i]) tmp[j+sumB[i]]=sumSon[j];

    int x=sumB[i],y=sumR[i];    //链上x个黑，y个红
    dp[i]=vector<int>(low[i]+sumB[i]+sumR[i] +1,inf);

    //通过把黑变0，最多变x个，dp[j]=min(dp[k]+(k-j)) j<=k<=j+x
    q.clear();
    rep(j,0,0+x-1){
        while(!q.empty()&&tmp[q.back()]+q.back()>=tmp[j]+j) q.pop_back();
        q.push_back(j);
    }
    rep(j,0,low[i]+x){
        //循环右端点为low[j]+x因为tmp[low[i]+x]往右均为inf
        if(!q.empty()&&q.front()<j) q.pop_front();
        if(j+x<=low[i]+x+y) {
            while(!q.empty()&&tmp[q.back()]+q.back()>=tmp[j+x]+(j+x)) q.pop_back();
            q.push_back(j+x);
        }
        dp[i][j]=min(dp[i][j],tmp[q.front()]+(q.front()-j));
    }

    //通过把红变1，最多变y个，dp[j]=min(dp[k]+(j-k)) j-y<=k<=y
    q.clear();
    per(j,low[i]+x+y,(low[i]+x+y)-y+1){
        while(!q.empty()&&tmp[q.back()]-q.back()>=tmp[j]-j) q.pop_back();
        q.push_back(j);
    }
    per(j,low[i]+x+y,x){
        //循环下界为x因为tmp[x]往左均为inf
        if(!q.empty()&&q.front()>j) q.pop_front();
        if(j-y>=0){
            while(!q.empty()&&tmp[q.back()]-q.back()>=tmp[j-y]-(j-y)) q.pop_back();
            q.push_back(j-y);
        }
        dp[i][j]=min(dp[i][j],tmp[q.front()]+(j-q.front()));
    }

    ans[i]=inf;
    rep(j,0,low[i]+x+y) ans[i]=min(ans[i],dp[i][j]);
}

int main(){
    int _;  cin>>_;
    while(_--){
        int n;    scanf("%d",&n);
        rep(i,1,n) G[i].clear();

        scanf("%s",s+1);
        rep(i,2,n) {
            int f;  scanf("%d",&f);
            G[f].pb(i);
        }

        // int m=1600; n=m*6+1;
        // rep(i,1,n) s[i]='0';
        // G[1].pb(2),G[1].pb(m+2);
        // rep(i,3,m+1) G[i-1].pb(i);
        // rep(i,m+3,m*2+1) G[i-1].pb(i);

        // G[m+1].pb(m*2+2),G[m+1].pb(m*3+2);
        // rep(i,m*2+3,m*3+1) G[i-1].pb(i);
        // rep(i,m*3+3,m*4+1) G[i-1].pb(i);

        // G[m*2+1].pb(m*4+2),G[m*2+1].pb(m*5+2);
        // rep(i,m*4+3,m*5+1) G[i-1].pb(i);
        // rep(i,m*5+3,m*6+1) G[i-1].pb(i);

        Dfs(1);
        Dfs2(1);

        rep(i,1,n) {
            printf("%d ",ans[ansFatherID[i]]);
        }
        printf("\n");
    }

    fflush(stdin); 
    getchar();
}
/*
2
9
101011110
1 1 3 3 3 6 2 2
4
1011
1 1 3
*/