You a given a permutation p1,p2,…,pnp1,p2,…,pn of size nn. Initially, all elements in pp are frozen. There will be nn stages that these elements will become available one by one. On stage ii, the element pkipki will become available.
For each ii, find the longest increasing subsequence among available elements after the first ii stages.
Input
The first line of the input contains an integer T(1≤T≤3)T(1≤T≤3), denoting the number of test cases.
In each test case, there is one integer n(1≤n≤50000)n(1≤n≤50000) in the first line, denoting the size of permutation.
In the second line, there are nn distinct integers p1,p2,...,pn(1≤pi≤n)p1,p2,...,pn(1≤pi≤n), denoting the permutation.
In the third line, there are nn distinct integers k1,k2,...,kn(1≤ki≤n)k1,k2,...,kn(1≤ki≤n), describing each stage.
It is guaranteed that p1,p2,...,pnp1,p2,...,pn and k1,k2,...,knk1,k2,...,kn are generated randomly.
Output
For each test case, print a single line containing nn integers, where the ii-th integer denotes the length of the longest increasing subsequence among available elements after the first ii stages.