题目描述

对于某个排列 p，萨库拉呼叫一个整数 j 从整数 i 可达，如果可以通过将 i=p[i] 一定次数后使 i 等于 j。

如果 p=[3,5,6,1,2,4]，那么，例如，4 是从 1 可达的，因为：i=1 → i=p[1]=3 → i=p[3]=6 → i=p[6]=4。现在 i=4，因此 4 是从 1 可达的。

排列中的每个数字都被涂上黑色或白色。

萨库拉定义函数 F(i) 为从 i 可达的黑色整数的数量。

萨库拉对每个 1≤i≤n 的 F(i) 感兴趣，但计算所有值变得非常困难，因此她请你作为她的好朋友来计算这个。

长度为 n 的排列是一个包含 n 个从 1 到 n 不同整数的数组，顺序可以任意。例如，[2,3,1,5,4] 是一个排列，但 [1,2,2] 不是排列（数字 2 在数组中出现两次），而 [1,3,4] 也不是排列（n=3，但数组中包含 4）。

输入

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

每个测试用例的第一行包含一个整数 n（1≤n≤2⋅10^5）——数组中元素的数量。

每个测试用例的第二行包含 n 个整数 p1,p2,…,pn（1≤pi≤n）——排列的元素。

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

可以保证所有测试用例中 n 的总和不超过 2⋅10^5。

输出

对于每个测试用例，输出 n 个整数 F(1), F(2), …, 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