CF2008D Sakurako's Hobby

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. $ ^{\text{∗}} $ 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 $ ).

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 $ .

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