CF1718A2.Burenka and Traditions (hard version)

This is the hard version of this problem. The difference between easy and hard versions is only the constraints on $a_i$ and on $n$. You can make hacks only if both versions of the problem are solved.

Burenka is the crown princess of Buryatia, and soon she will become the $n$-th queen of the country. There is an ancient tradition in Buryatia — before the coronation, the ruler must show their strength to the inhabitants. To determine the strength of the $n$-th ruler, the inhabitants of the country give them an array of $a$ of exactly $n$ numbers, after which the ruler must turn all the elements of the array into zeros in the shortest time. The ruler can do the following two-step operation any number of times:

• select two indices $l$ and $r$, so that $1 \le l \le r \le n$ and a non-negative integer $x$, then
• for all $l \leq i \leq r$ assign $a_i := a_i \oplus x$, where $\oplus$ denotes the bitwise XOR operation. It takes $\left\lceil \frac{r-l+1}{2} \right\rceil$ seconds to do this operation, where $\lceil y \rceil$ denotes $y$ rounded up to the nearest integer.

Help Burenka calculate how much time she will need.

这是本题的困难版本。简单版本与困难版本的唯一区别在于对 $a_i$ 和 $n$ 的约束条件不同。仅当两个版本均已被解决时，才允许进行 Hack。

布尔恩卡是布里亚特共和国的王储，她即将成为该国第 $n$ 位女王。布里亚特有一项古老传统：加冕前，统治者必须向国民展示自身的力量。为判定第 $n$ 位统治者的力量，国民会提供一个恰好包含 $n$ 个数字的数组 $a$；随后，统治者必须在最短时间内将该数组的所有元素全部变为零。统治者可执行以下两步操作任意多次：

• 选择两个下标 $l$ 和 $r$，满足 $1 \le l \le r \le n$，并选择一个非负整数 $x$，然后
• 对所有满足 $l \leq i \leq r$ 的下标 $i$，令 $a_i := a_i \oplus x$，其中 $\oplus$ 表示按位异或运算。该操作耗时 $\left\lceil \frac{r-l+1}{2} \right\rceil$ 秒，其中 $\lceil y \rceil$ 表示将 $y$ 向上取整至最近的整数。

请帮助布尔恩卡计算她完成任务所需的最短时间。

The first line contains a single integer $t$ $(1 \le t \le 500)$ — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ $(1 \le n \le 10^5)$ - the size of the array

The second line of each test case contains $n$ integers $a_1, a_2, \cdots , a_n$ $(0 \le a_i \lt 2^{30})$ — elements of the array.

It is guaranteed that the sum of $n$ in all tests does not exceed $10^5$.

第一行包含一个整数 $t$（$1 \le t \le 500$）—— 表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$）—— 表示数组的大小。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \cdots , a_n$（$0 \le a_i \lt 2^{30}$）—— 表示数组的元素。

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

For each test case, output a single number — the minimum time that Burenka will need.

对于每个测试用例，输出一个数字——Burenka 所需的最少时间。

In the first test case, Burenka can choose segment $l = 1$, $r = 4$, and $x=5$. so it will fill the array with zeros in $2$ seconds.

In the second test case, Burenka first selects segment $l = 1$, $r = 2$, and $x = 1$, after which $a = [0, 2, 2]$, and then the segment $l = 2$, $r = 3$, and $x=2$, which fills the array with zeros. In total, Burenka will spend $2$ seconds.

在第一个测试用例中，Burenka 可以选择区间 $l = 1$、$r = 4$，以及 $x=5$，从而在 $2$ 秒内将数组全部填为零。

在第二个测试用例中，Burenka 首先选择区间 $l = 1$、$r = 2$，以及 $x = 1$，操作后数组变为 $a = [0, 2, 2]$；然后选择区间 $l = 2$、$r = 3$，以及 $x=2$，从而将数组全部填为零。总计，Burenka 将花费 $2$ 秒。