A16474 | Al Fine (Maximizing Version)

这是该问题的最大化版本。与其他版本的不同之处在于，在本版本中，你需要找到所有“公共树”中可能的最大深度。此外，本版本对于 $n$ 的限制更大。只有在你解决了所有版本的本题后，才能进行 hack。

在圣诞节，Tortinita 和 Arietta 各自都得到了一个圣诞树。巧合的是，她们的树拥有完全相同的性质：两棵树均有 $n+1$ 个结点，且都以结点 $0$ 作为根节点。在她们寄给你的圣诞贺卡中，会在祝福语后附上一个各自的树的 DFS 序列。回忆一下，DFS 序列是通过如下伪代码生成的。

```
dfs_order = []
def dfs(v):
dfs_order.append(v)
pick an arbitrary permutation s of children of v
for child in s:
dfs(child)

dfs(root)
```

设 Tortinita 的树的 DFS 序列为 $a_0, a_1, \ldots, a_n$，Arietta 的树的 DFS 序列为 $b_0, b_1, \ldots, b_n$。你注意到 $a_0=b_0=0$，而且因为她们是双胞胎姐妹，你想知道她们是否可能选到完全相同的树。你还觉得，姐妹们的圣诞树绝不会选平凡的结构。因此，你希望求出所有公共树中可能的最大深度 $^{\text{∗}}$。

$^{\text{∗}}$ 树的深度定义为任意节点到根节点的简单路径上的最大边数。

每组测试数据包含多组测试用例。第一行包含测试用例的数量 $t$（$1\leq t \leq 10^4$）。接下来为每组测试用例的描述。

每组测试用例的第一行包含一个整数 $n$（$2\leq n \leq 10^6$）。

第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$（$1 \leq a_i \leq n$）。

第三行包含 $n$ 个整数 $b_1, b_2, \cdots, b_n$（$1 \leq b_i \leq n$）。

保证序列 $a$ 和 $b$ 均无重复元素。

保证所有测试用例中 $n$ 的和不超过 $10^6$。

对于每组测试用例，输出一个整数——所有公共树中可能的最大深度。