#include<bits/stdc++.h>

#define vc vector
#define pb emplace_back
#define pii pair<int, int>
#define mkp make_pair
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define lep(i, a, b) for(int i = (a); i >= (b); --i)

using namespace std;

inline int read() {
	int x = 0, w = 0; char ch = getchar(); while(!isdigit(ch)) w |= (ch == '-'), ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar(); return w ? -x : x; 
}

const int N = 1e5 + 5, inf = 1e9;

int n, a[N], ans[N];
int DFN, fa[N], dfn[N], son[N], h[N], le[N], ri[N], b[N], r[N];
char str[N];
vc<int> G[N]; 

namespace sgt {
	int tre1[N << 3], tre2[N << 3];
	#define mid (l + r >> 1)
	#define ls (k << 1)
	#define rs (k << 1 | 1)
	inline void build(int k, int l, int r) {
		tre1[k] = tre2[k] = inf;
		if(l != r) build(ls, l, mid), build(rs, mid + 1, r);
	}
	inline void psu(int k) { tre1[k] = min(tre1[ls], tre1[rs]); tre2[k] = min(tre2[ls], tre2[rs]); } 
	inline void ins(int k, int l, int r, int p, int v) {
		if(l == r) return tre1[k] = v - l, tre2[k] = v + l, void(); 
		return (p <= mid ? ins(ls, l, mid, p, v) : ins(rs, mid + 1, r, p, v)), psu(k);
	}
	inline int ask1(int k, int l, int r, int L, int R) {
		if(L > R || L > r || R < l) return inf;
		if(L <= l && R >= r) return tre1[k];
		return min(ask1(ls, l, mid, L, R), ask1(rs, mid + 1, r, L, R));
	}
	inline int ask2(int k, int l, int r, int L, int R) {
		if(L > R || L > r || R < l) return inf;
		if(L <= l && R >= r) return tre2[k];
		return min(ask2(ls, l, mid, L, R), ask2(rs, mid + 1, r, L, R));
	}
}
using namespace sgt;

inline void dfs1(int x) {
	son[x] = 0; 
	for(auto y : G[x]) {
		dfs1(y);
		son[x] = h[y] > h[son[x]] ? y : son[x];
	}
	h[x] = h[son[x]] + 1;
}

inline void dfs2(int x) {
	dfn[x] = ++DFN;
	if(!son[x]) {
		le[x] = DFN; ri[x] = ++DFN; 
		h[x] = 1; b[x] = r[x] = 0;
		return ;
	}
	
	for(auto y : G[x]) dfs2(y);
	
	if(G[x].size() == 1) {
		le[x] = le[son[x]]; ri[x] = ri[son[x]];
		h[x] = h[son[x]]; b[x] = b[son[x]]; r[x] = r[son[x]];
		if(a[x]) ++b[x]; 
		else ++r[x];
		return ;
	}
	
	for(auto y : G[x]) h[x] = min(h[x], h[y] + 1);
	le[x] = dfn[x]; ri[x] = dfn[x] + h[x]; b[x] = r[x] = 0;
}

inline int query(int x, int i) {
	int res = inf;
	res = min(res, ask1(1, 1, DFN, max(le[x], le[x] + i - r[x] - b[x]), min(ri[x], le[x] + i - b[x])) + le[x] + i - b[x]);
	res = min(res, ask2(1, 1, DFN, max(le[x], le[x] + i - b[x]), min(ri[x], le[x] + i)) - le[x] - i + b[x]);
	return res;
}

inline void dfs3(int x) {
	if(!son[x]) {
		ans[x] = 0; 
		ins(1, 1, DFN, le[x], a[x] ? 1 : 0);
		ins(1, 1, DFN, ri[x], a[x] ? 0 : 1);
		return ;
	}
	
	for(auto y : G[x]) dfs3(y);
	
	if(G[x].size() == 1) {
		ans[x] = ans[son[x]];
		return ;
	}
	
	vc<int> dp(h[x] + 1, 0); ans[x] = inf;
	for(auto y : G[x]) 
		rep(i, 0, h[x] - 1) 
			dp[i] += query(y, i);
	
	if(a[x]) {
		lep(i, h[x], 1) dp[i] = dp[i - 1]; dp[0] = inf;
		rep(i, 0, h[x] - 1) dp[i] = min(dp[i], dp[i + 1] + 1);
	}
	else {
		dp[h[x]] = inf;
		rep(i, 1, h[x]) dp[i] = min(dp[i], dp[i - 1] + 1);
	}
	rep(i, 0, h[x]) ins(1, 1, DFN, le[x] + i, h[x]), ans[x] = min(ans[x], dp[i]);
}

inline void testcase() {
	n = read(); scanf("%s", str + 1);
	rep(i, 1, n) a[i] = str[i] - '0', G[i].clear();
	
	rep(i, 2, n) fa[i] = read(), G[fa[i]].pb(i);
	
	DFN = 0; dfs1(1); dfs2(1);
	
	build(1, 1, DFN);
	dfs3(1);
	
	rep(i, 1, n) printf("%d%c", ans[i], " \n"[i == n]);
}

signed main() {
	int t = read(); while(t--) testcase(); 
	return 0;
}