#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define see(x) cerr << x << " "
#define seeln(x) cerr << x << endl
#define out(x) cerr << #x << " = " << x << " "
#define outln(x) cerr << #x << " = " << x << endl

#define re
inline void Rd(int &res){
    re char c;res=0;
    while(c=getchar(),c<48);
    do res=(res<<3)+(res<<1)+(c^48);
    while(c=getchar(),c>47);
}

const int N = 100005;
int n;
int col[N];
char str[N];
vector<int> G[N];

struct node {
	int src;
	int cnt;
	int k;
};

const int inf = 1000000000;
int len[N];
int ans[N];
int Log[N];
int vA[N][19], vB[N][19];

void dfs(int x) {
	if (G[x].empty()) {
		len[x] = 1;
		return;
	}
	len[x] = inf;
	for (int y : G[x]) {
		dfs(y);
		if (len[y] + 1 < len[x]) {
			len[x] = len[y] + 1;
		}
	}
}

#define sz(x) (int)(x.size())
vector<int> dp[N], Dp[N];
int sum[N];
node cur[N];

int calcdp(int x, int id) {
	// out(x); out(id); outln(sz(dp[x]));
	if (id < 0 || id > len[x]) return inf;
	return dp[x][id];
}
int calcDp(int x, int id) {
	if (id < 0 || id > len[x]) return inf;
	return Dp[x][id];
}

int qA(int l, int r) {
	int k = Log[r - l + 1];
	return min(vA[l][k], vA[r - (1 << k) + 1][k]);
}
int qB(int l, int r) {
	int k = Log[r - l + 1];
	return min(vB[l][k], vB[r - (1 << k) + 1][k]);
}

void calc_top(int x) {
	int y = cur[x].src;
	int k = cur[x].k;
	int cnt = cur[x].cnt;
	// out(x); out(y); out(k); outln(cnt);
	Dp[x].resize(len[x] + 1);
	for (int i = 0; i <= len[x]; ++i) {
		Dp[x][i] = inf;
		vA[i][0] = vB[i][0] = inf;
	}
	for (int i = 0; i <= len[y] && i <= len[x]; ++i) {
		vA[i][0] = dp[y][i] + i;
		vB[i][0] = dp[y][i] - i;
	}
	/*for (int i = 0; i <= len[x]; ++i) {
		out(i); out(vA[i][0]); outln(vB[i][0]);
	}*/
	for (int i = 1; i <= Log[len[x]]; ++i) {
		for (int j = 0; j <= len[x] - (1 << i) + 1; ++j) {
			vA[j][i] = min(vA[j][i - 1], vA[j + (1 << (i - 1))][i - 1]);
			vB[j][i] = min(vB[j][i - 1], vB[j + (1 << (i - 1))][i - 1]);
		}
	}
	/*for (int i = 0; i <= len[x]; ++i) {
		for (int j = i; j <= len[x]; ++j) {
			out(i); out(j); out(qA(i, j)); outln(qB(i, j));
		}
	}*/
	for (int i = 0; i <= len[x]; ++i) {
		/*for (int j = 0; j <= i && j <= k; ++j) {
			Dp[x][i] = min(Dp[x][i], calcdp(y, i - j) + abs(cnt - j));
		}*/
		int s1, s2;
		s1 = i - min(i, min(k, cnt)), s2 = i - 0;
		if (s1 <= s2) {
			Dp[x][i] = min(Dp[x][i], qA(s1, s2) + cnt - i);
			/*for (int k = s1; k <= s2; ++k) {
				Dp[x][i] = min(Dp[x][i], calcdp(y, k) + k + cnt - i);
			}*/
		}
		s1 = i - min(i, k), s2 = i - (cnt + 1);
		if (s1 <= s2) {
			Dp[x][i] = min(Dp[x][i], qB(s1, s2) + i - cnt);
			/*for (int k = s1; k <= s2; ++k) {
				Dp[x][i] = min(Dp[x][i], calcdp(y, k) - k + i - cnt);
			}*/
		}
		/*for (int j = 0; j <= i && j <= k && j <= cnt; ++j) {
			Dp[x][i] = min(Dp[x][i], calcdp(y, i - j) + i - j + cnt - i);
		}
		for (int j = cnt + 1; j <= i && j <= k; ++j) {
			Dp[x][i] = min(Dp[x][i], calcdp(y, i - j) + j - i + i - cnt);
		}*/
	}
}

node run(int x) {
	if (sz(G[x]) == 0) {
		cur[x] = (node){x, 0, 0};
		dp[x] = {0, 0};
		if (col[x]) dp[x][0] = 1;
		else dp[x][1] = 1;
		// out(x); outln(cur[x].src);
		return cur[x];
	}
	if (sz(G[x]) == 1) {
		node tmp = run(G[x][0]);
		tmp.k += 1;
		tmp.cnt += col[x];
		ans[x] = ans[G[x][0]];
		cur[x] = tmp;
		return tmp;
	}
	for (int y : G[x]) run(y);


	// see("run"); outln(x);


	dp[x].resize(len[x] + 1);
	for (int i = 0; i <= len[x]; ++i) {
		sum[i] = 0;
		dp[x][i] = inf;
	}
	for (int y : G[x]) {
		if (dp[y].empty()) {
			calc_top(y);
			for (int i = 0; i <= len[x]; ++i) {
				sum[i] = min(sum[i] + calcDp(y, i), inf);
			}
		} else {
			for (int i = 0; i <= len[x]; ++i) {
				sum[i] = min(sum[i] + calcdp(y, i), inf);
			}
		}
	}


	if (col[x]) {
		for (int h = 0; h <= len[x]; ++h) {
			int tmp = inf;
			tmp = min(tmp, sum[h] + 1);
			if (h) tmp = min(tmp, sum[h - 1]);
			dp[x][h] = tmp;
		}
	} else {
		for (int h = 0; h <= len[x]; ++h) {
			int tmp = inf;
			tmp = min(tmp, sum[h]);
			if (h) tmp = min(tmp, sum[h - 1] + 1);
			dp[x][h] = tmp;
		}
	}
	ans[x] = inf;
	for (int i = 0; i <= len[x]; ++i) {
		ans[x] = min(ans[x], dp[x][i]);
	}
	return (node){x, 0, 0};
}

void clear() {
	for (int i = 1; i <= n; ++i) {
		G[i].clear();
		dp[i].clear();
		Dp[i].clear();
	}
	for (int i = 0; i <= n; ++i) sum[i] = 0;
	for (int i = 0; i <= n; ++i) col[i] = 0;
	for (int i = 0; i <= n; ++i) len[i] = 0;
	for (int i = 0; i <= n; ++i) ans[i] = 0;
	for (int i = 0; i <= n; ++i) cur[i] = (node){0, 0, 0};
}

int main() {
	int T; Rd(T); while (T--) {
		Rd(n);
		scanf("%s", str + 1);
		for (int i = 1; i <= n; ++i) col[i] = str[i] - 48;
		Log[0] = -1;
		for (int i = 1; i <= n; ++i) {
			Log[i] = Log[i >> 1] + 1;
		}
		for (int i = 2; i <= n; ++i) {
			int u; scanf("%d", &u);
			G[u].push_back(i);
		}
		dfs(1); run(1);
		for (int i = 1; i <= n; ++i) printf("%d%c", ans[i], " \n"[i == n]);
		clear();
	}
	return 0;
}