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.

Input

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$.

Output

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

见题面 Input 部分

见题面 Output 部分

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.