There is a rooted tree of $n$ vertices with the root in vertex $1$, each vertex has zero or one **heavy child** linked with a **heavy edge**, a set of maximal connected heavy edges form a **heavy chain**. A single vertex can also form a heavy chain, so each vertex belongs to exactly one heavy chain.

Now we want to build a search tree to maintain some information of the original tree. For each heavy chain with $k$ vertices, we construct a segment tree of depth $\lceil \log_22k \rceil$ to maintain it, with each leaf of the segment tree indicating a vertex on the heavy chain, and the parent of the segment tree's root is the parent of the top vertex of the heavy chian.

Note that in our variant of the segment tree, every leaves have the same depth.

For instance, this is a possible original tree, note that a double slash indicating a heavy edge.


                    1
                  // \
                  2   7
                //    \\
                3       8
              //        \\
              4           9
            // \
            5  10
           /
          6


There are $4$ heavy chain in this tree. They are:

1->2->3->4->5
6
7->8->9
10


This is the search tree of the previous origin tree, note that the double slash here has no special meaning, just make the search tree looks more beautiful.


                    o
                  // \\
                 o     o
               // \\   //
              o    o   o
             / \  / \ /
            1  2 3  4 5
            |       | |
            o      10 6
           / \
          o   o
         / \  /
        7   8 9



Given such a original tree, your task is to calculate the depth of the search tree. The depth of the root is $1$.

The first line of the input contains an integer $T\ (1\le T \le 20)$ , indicating the number of the test cases.

For each test case:

The first line of the input contains an interger $n\ (1\le n\le 10^6)$ , indicating the number of the vertices in the original tree.

The next lines has $n$ integers, indicating the parent of each vertex. Note that $0$ indicating don't have a parent.

The next lines has $n$ integers, indicating the heavy child of each vertex. Note that $0$ indicating don't have a heavy child.

It's guaranteed that $\sum n\le 10^7$.

$T$ lines, each line has one interger, indicating the answer.

Note that the input scale is **extremely** large.

Notes: In this problem, you may need more stack space to pass this problem. We suggest you to add the following code into your main function if you use C++.

int main() {
    int size(512<<20); // 512M
    __asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size)); // YOUR CODE
    ...
    exit(0);
}

And if you use the code above please DON’T forget to add exit(0); in the end of your main function, otherwise your code may get RE.

2023“钉耙编程”中国大学生算法设计超级联赛（5）