write a go solution for Description:
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<=l<=r<=n and a non-negative integer x, then
- for all l<=i<=r assign a_i:=a_ioplusx, where oplus denotes the bitwise XOR operation. It takes ceil(r-l+1/2) seconds to do this operation, where ceil(y) denotes y rounded up to the nearest integer.

Help Burenka calculate how much time she will need.

Input Format:
The first line contains a single integer t (1<=t<=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<=n<=10^5) - the size of the array

The second line of each test case contains n integers a_1,a_2,*s,a_n (0<=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 Format:
For each test case, output a single number  — the minimum time that Burenka will need.

Note:
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.. Output only the code with no comments, explanation, or additional text.