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

If $p=[3,5,6,1,2,4]$, then, for example, $4$ is reachable from $1$, because: $i=1$ $\rightarrow$ $i=p_1=3$ $\rightarrow$ $i=p_3=6$ $\rightarrow$ $i=p_6=4$. Now $i=4$, so $4$ is reachable from $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\le i\le n$, but calculating all values becomes very difficult, so she asks you, as her good friend, to compute this.

Input

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

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

The second line of each test case contains $n$ integers $p_1, p_2, \dots, p_n$ ($1\le p_i\le 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 $s_i=0$, then the number $p_i$ is colored black; if $s_i=1$, then the number $p_i$ is colored white.

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

Output

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

见题面 Input 部分

见题面 Output 部分