CF1720D2 Xor-Subsequence (hard version)

这是此问题的困难版本。简单版本与困难版本的唯一区别在于：在困难版本中，$a_i\leq 10^9$。 给你一个长为 $n$ 的整数数组 $a$，从 $0$ 开始编号。 一个长为 $m$ ，从 $0$ 开始编号的整数数组 $b$ 是数组 $a$ 的 subsequence，当且仅当 $0\leq b_0

第一行一个整数 $T$，表示数据组数。 对于每组数据，第一行一个整数 $n$，表示数组 $a$ 的长度。 第二行有 $n$ 个整数，表示数组 $a$。

对于每组数据，输出一行一个数，表示最长的 beautiful subsequence 的长度。

$1\leq T\leq 10^5,2\leq n\leq 3\times 10^5,0\leq a_i\leq 10^9,\sum n\leq 3\times 10^5$。