A15331 | 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](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). 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.