该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem

For a certain permutation $p∗$ Sakurako calls an integer $j$ reachable from an integer $i$ if it is possible to make $i$ equal to $j$ by assigning $i=pi$ a certain number of times.

If $p=[3,5,6,1,2,4],$ then, for example,$4$ is reachable from $1,$ because: $i=1 →i=p1=3→i=p3=6→i=p6=4.$ Now $i=4,$ so $4$ is reachablefrom $1.$

Each number in the permutation is colored either black or white.

Sakurako defines the function $F(i)$ as the number of black integers that are reachable from $i.$

Sakurako is interested in $F(i)$ for each $1≤i≤n,$ but calculating all values becomes very difficult, so she asks you, as her good friend, to compute this.

$∗A$ permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation (the number $2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ( $n=3,$ but the array contains $4$ ).

Input

The first line contains a single integer $t$ $(1≤t≤10^4)$ — the number of test cases.

The first line of each test case contains a single integer $n$ $(1≤n≤10^5)$ — the number of elements in the array.

The second line of each test case contains $n$ integers $p1,p2,…,pn (1≤pi≤n)$ — the elements of the permutation.

The third line of each test case contains a string $s$ of length $n,$ consisting of '0' and '1'. If $si=0,$ then the number $pi$ is colored black; if $si=1,$ then the number $pi$ is colored white.

It is guaranteed that the sum of $n$ across all test cases does not exceed $5⋅10^5$ .

Output

For each test case, output $n$ integers $F(1),F(2),…,F(n).$

Example : in

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

Example : out

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