#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>

using namespace std;

const int max1 = 1e5;
const int inf = 0x3f3f3f3f;

int T, n;
char s[max1 + 5];
vector <int> edge[max1 + 5];

int mindeep[max1 + 5], id[max1 + 5], cnt[max1 + 5];
vector <int> f[max1 + 5];
int ans[max1 + 5];

int tmp[max1 + 5], total;

deque <int> que;

void Dfs ( int now )
{
    f[now].clear();
    if ( edge[now].empty() )
    {
        mindeep[now] = 1;

        id[now] = now;
        f[now].push_back(s[now] == '1');
        f[now].push_back(s[now] == '0');
        cnt[now] = 0;

        ans[now] = 0;
    }
    else
    {
        mindeep[now] = inf;
        for ( auto v : edge[now] )
            Dfs(v), mindeep[now] = min(mindeep[now], mindeep[v]);
        ++mindeep[now];
        
        if ( edge[now].size() == 1 )
        {
            id[now] = id[edge[now][0]];
            cnt[now] = cnt[edge[now][0]] + (s[now] == '1');
            ans[now] = ans[id[now]];
        }
        else
        {
            id[now] = now;
            cnt[now] = 0;

            for ( auto v : edge[now] )
            {
                total = mindeep[id[v]];
                for ( int i = 0; i <= total; i ++ )
                    tmp[i] = f[id[v]][i];
                f[id[v]].clear();

                int Min = inf; que.clear();
                for ( int i = 0; i <= mindeep[now] - 1; i ++ )
                {
                    if ( i - cnt[v] >= 0 && i - cnt[v] <= total )
                        Min = min(Min, tmp[i - cnt[v]] - (i - cnt[v]));
                    
                    if ( i <= total )
                    {
                        while ( !que.empty() && tmp[que.back()] + que.back() >= tmp[i] + i )
                            que.pop_back();
                        que.push_back(i);
                    }

                    while ( !que.empty() && que.front() <= i - cnt[v] )
                        que.pop_front();
                    
                    f[id[v]].push_back(inf);
                    f[id[v]].back() = min(f[id[v]].back(), Min + i - cnt[v]);
                    if ( !que.empty() )
                        f[id[v]].back() = min(f[id[v]].back(), tmp[que.front()] + que.front() + cnt[v] - i);
                    
                    // printf("now = %d i = %d v = %d f = %d\n", now, i, v, f[id[v]].back());
                }
            }

            ans[now] = inf;
            for ( int i = 0; i <= mindeep[now]; i ++ )
            {
                f[now].push_back(inf);
                int sum;
                if ( i != 0 )
                {
                    sum = s[now] == '0';
                    for ( auto v : edge[now] )
                        sum += f[id[v]][i - 1];
                    
                    f[now].back() = min(f[now].back(), sum);
                }

                if ( i != mindeep[now] )
                {
                    sum = s[now] == '1';
                    for ( auto v : edge[now] )
                        sum += f[id[v]][i];
                    
                    f[now].back() = min(f[now].back(), sum);
                }
                
                ans[now] = min(ans[now], f[now].back());
            }
        }
    }
    return;
}

void Work ()
{
    int fa;
    scanf("%d%s", &n, s + 1);
    for ( int i = 1; i <= n; i ++ )
        edge[i].clear();
    for ( int i = 2; i <= n; i ++ )
        scanf("%d", &fa), edge[fa].push_back(i);
    
    Dfs(1);

    for ( int i = 1; i <= n; i ++ )
        printf("%d ", ans[i]);
    printf("\n");

    return;
}

int main ()
{
    scanf("%d", &T);
    while ( T -- )
        Work();

    return 0;
}