CF2018E2.Complex Segments (Hard Version)

这是这个问题的困难版本。在这个版本中， $n$ 的范围和时间限制都变高了。

当一个区间的集合可以被分割成一些子集并满足以下条件时，这个集合是复杂的：

• 所有的子集的大小相同
• 当且仅当两个区间在同一子集内时，这两个区间相交。

$t$ 组数据，每组数据给你一个集合包含 $n$ 个区间 $[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]$。求出最大的子集满足其为复杂的，输出这个集合的大小。

第一行输入数据个数 $t(1 \le t \le 10^3)$。

每个数据的第一行包含一个整数 $n(1 \le n \le 3 \cdot 10^5)$，集合的区间个数。

每个数据的第二行包含 $n$ 个整数 $l_1, l_2, \ldots, l_n(1 \le l_i \le 2n)$，分别表示这 $n$ 个区间的左端点。

每个数据的第三行包含 $n$ 个整数 $r_1, r_2, \ldots, r_n(l_i \leq r_i \le 2n)$，分别表示这 $n$ 个区间的右端点。

保证所有数据 $n$ 的总和不超过 $3 \cdot 10^5$。

对于每个数据输出一行表示最大的复杂的子集的大小。