D. 樱子的爱好

每个测试的时间限制：2 秒
内存限制：256 兆字节

---

题目描述

对于某个排列 $p$，樱子称整数 $j$ 可以从整数 $i$ 到达，如果可以通过若干次将 $i$ 赋值为 $p_i$ 的操作使得 $i$ 等于 $j$。

例如，如果 $p = [3,5,6,1,2,4]$，那么 $4$ 可以从 $1$ 到达，因为：

$$1 \rightarrow p_1 = 3 \rightarrow p_3 = 6 \rightarrow p_6 = 4 $$

此时 $i = 4$，所以 $4$ 可以从 $1$ 到达。

排列中的每个数被染成黑色或白色。

樱子定义函数 $F(i)$ 为从 $i$ 出发可以到达的黑色整数的数量。

樱子对每个 $1 \le i \le n$ 的 $F(i)$ 很感兴趣，但计算所有值变得非常困难，所以她作为你的好朋友，请你帮忙计算。

---

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$）—— 排列中元素的数量。

每个测试用例的第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$（$1 \le p_i \le n$）—— 排列的元素。

每个测试用例的第三行包含一个长度为 $n$ 的字符串 $s$，由 '0' 和 '1' 组成。如果 $s_i = 0$，则数字 $p_i$ 被染成黑色；如果 $s_i = 1$，则数字 $p_i$ 被染成白色。

保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

---

输出格式

对于每个测试用例，输出 $n$ 个整数 $F(1), F(2), \dots, F(n)$。

---

输入样例

5
1
1
0
5
1 2 4 5 3
10101
5
5 4 1 3 2
10011
6
3 5 6 1 2 4
010000
6
1 2 3 4 5 6
100110

---

输出样例

1 
0 1 1 1 1 
2 2 2 2 2 
4 1 4 4 1 4 
0 1 1 0 0 1