A permutation of integers from $$$1$$$ to $$$n$$$ is an array of size $$$n$$$ where each integer from $$$1$$$ to $$$n$$$ appears exactly once.

You are given a permutation $$$p$$$ of integers from $$$1$$$ to $$$n$$$. You have to process $$$n$$$ queries. During the $$$i$$$-th query, you replace $$$p_{d_i}$$$ with $$$0$$$. Each element is replaced with $$$0$$$ exactly once. The changes made in the queries are saved, that is, after the $$$i$$$-th query, all integers $$$p_{d_1}, p_{d_2}, \dots, p_{d_i}$$$ are zeroes.

After each query, you have to find the minimum number of operations required to fix the array; in other words, to transform the current array into any permutation of integers from $$$1$$$ to $$$n$$$ (possibly into the original permutation $$$p$$$, possibly into some other permutation).

The operation you can perform to fix the array is the following one:

choose the integer $$$i$$$ from $$$1$$$ to $$$n$$$, replace the $$$i$$$-th element of the array with $$$i$$$.

Note that the answer for each query is calculated independently, meaning you do not actually apply any operations, just calculate the minimum number of operations.

Input

Each test consists of several test cases. The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — the number of test cases. Then the test cases follow.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^{5}$$$).

The second line of each test case contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_{i} \le n$$$) — the original permutation. All $$$p_i$$$ are distinct.

The third line of each test case contains $$$n$$$ integers $$$d_1, d_2, \dots, d_n$$$ ($$$1 \le d_{i} \le n$$$). All $$$d_{i}$$$ are distinct.

Additional constraint on the input:

the sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^{5}$$$.

Output

For each test case, output a line containing $$$n$$$ integers, where the $$$i$$$-th integer should be equal to the minimum number of operations required to fix the array which was obtained after the $$$i$$$-th query (i.e., the permutation $$$p$$$ where all integers $$$p_{d_1}, p_{d_2}, \dots, p_{d_i}$$$ are replaced by zeroes).

Note

In the first test case, after each query, every integer which was replaced by $$$0$$$ can be restored by one operation.

In the second test case, you can act as follows:

Query $$$1$$$: $$$p = [4, 5, 3, 0, 2]$$$, it can be transformed into $$$[{\color{red}1}, 5, 3, {\color{red}4}, 2]$$$.
Query $$$2$$$: $$$p = [4, 5, 3, 0, 0]$$$, it can be transformed into $$$[{\color{red}1}, {\color{red}2}, 3, {\color{red}4}, {\color{red}5}]$$$.
Query $$$3$$$: $$$p = [0, 5, 3, 0, 0]$$$, it can be transformed into $$$[{\color{red}1}, {\color{red}2}, 3, {\color{red}4}, {\color{red}5}]$$$.
Query $$$4$$$: $$$p = [0, 5, 0, 0, 0]$$$, it can be transformed into $$$[{\color{red}1}, {\color{red}2}, {\color{red}3}, {\color{red}4}, {\color{red}5}]$$$.
Query $$$5$$$: $$$p = [0, 0, 0, 0, 0]$$$, it can be transformed into $$$[{\color{red}1}, {\color{red}2}, {\color{red}3}, {\color{red}4}, {\color{red}5}]$$$.

The numbers that were changed are highlighted in red.

Idx	Name	Rating
A	Cloudberry Jam	800
B	Large Array and Segments	1100
C	Disappearing Permutation	1300
D	Even String	1700
E	Zebra-like Numbers	2400
F	Online Palindrome	3000

Educational Codeforces Round 177 (Rated for Div. 2)