#include<bits/stdc++.h>
using namespace std;
#define Re register int

const int N = 100005, Inf = 1000000;
map<int, int> f[N];
int T, n, cnt, col[N], hea[N], nxt[N], to[N], d[N], dd[N], h[N], ans[N], dq1[N], dq2[N], g1[N], g2[N];
char s[N];

inline void add(int x, int y)
{
	nxt[++cnt] = hea[x], to[cnt] = y, hea[x] = cnt, ++d[x];
}

inline void dfs(int x)
{
	int q[2], y = x, he = 1, v = 0;
	q[0] = q[1] = 0, q[col[x]] = 1, ans[y] = N;
	while (d[x] == 1) x = to[hea[x]], ++q[col[x]], ++he;
	if (!hea[x]) h[y] = he;
	else h[y] = Inf;
	for (Re i = hea[x]; i; i = nxt[i])
	{
		int u = to[i];
		dfs(u);
		h[y] = min(h[y], he + h[u]);
	}
	for (Re i = hea[x]; i; i = nxt[i]) dd[++v] = to[i];
	int l1 = 1, r1 = 0, l2 = 1, r2 = 0;
	for (Re i = 0; i <= h[y]; ++i)
	{
		g1[i] = i, g2[i] = -i;
		if (i > h[y] - he) g1[i] = g2[i] = Inf;
		else for (Re j = 1; j <= v; ++j) g1[i] += f[dd[j]][i], g2[i] += f[dd[j]][i];
		while (l1 <= r1 && i - dq1[l1] > q[1]) ++l1;
		while (l1 <= r1 && g1[dq1[r1]] >= g1[i]) --r1;
		dq1[++r1] = i;
		f[y][i] = g1[dq1[l1]] + q[1] - i;
		if (i >= q[1] + 1)
		{
			while (l2 <= r2 && i - dq2[l2] > q[0] + q[1]) ++l2;
			while (l2 <= r2 && g2[dq2[r2]] >= g2[i - q[1] - 1]) --r2;
			dq2[++r2] = i - q[1] - 1;
			f[y][i] = min(f[y][i], g2[dq2[l2]] + i - q[1]);
		}
		ans[y] = min(ans[y], f[y][i]);
		//printf("!!%d %d %d\n", y, i, f[y][i]);
	}
	x = y;
	while (d[x] == 1) x = to[hea[x]], ans[x] = ans[y];
}

int main()
{
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d", &n);
		scanf("%s", s + 1);
		cnt = 0;
		for (Re i = 1; i <= n; ++i) col[i] = (s[i] == 49), hea[i] = d[i] = 0, f[i].clear();
		for (Re i = 2; i <= n; ++i)
		{
			int u;
			scanf("%d", &u);
			add(u, i);
		}
		dfs(1);
		for (Re i = 1; i < n; ++i) printf("%d ", ans[i]);
		printf("%d\n", ans[n]);
	}
	return 0;
}