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.

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 < 2^{30})$ — elements of the array.

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

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

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.