#P1718A2. Burenka and Traditions (hard version)

Burenka and Traditions (hard version)

Description

This is the hard version of this problem. The difference between easy and hard versions is only the constraints on aia_i and on nn. 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 nn-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 nn-th ruler, the inhabitants of the country give them an array of aa of exactly nn 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 ll and rr, so that 1lrn1 \le l \le r \le n and a non-negative integer xx, then
  • for all lirl \leq i \leq r assign ai:=aixa_i := a_i \oplus x, where \oplus denotes the bitwise XOR operation. It takes rl+12\left\lceil \frac{r-l+1}{2} \right\rceil seconds to do this operation, where y\lceil y \rceil denotes yy rounded up to the nearest integer.

Help Burenka calculate how much time she will need.

The first line contains a single integer tt (1t500)(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 nn (1n105)(1 \le n \le 10^5) - the size of the array

The second line of each test case contains nn integers a1,a2,,ana_1, a_2, \cdots , a_n (0ai<230)(0 \le a_i < 2^{30}) — elements of the array.

It is guaranteed that the sum of nn in all tests does not exceed 10510^5.

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

Input

The first line contains a single integer tt (1t500)(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 nn (1n105)(1 \le n \le 10^5) - the size of the array

The second line of each test case contains nn integers a1,a2,,ana_1, a_2, \cdots , a_n (0ai<230)(0 \le a_i < 2^{30}) — elements of the array.

It is guaranteed that the sum of nn in all tests does not exceed 10510^5.

Output

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

Samples

样例输入 1

<div class="test-example-line test-example-line-even test-example-line-0">7</div><div class="test-example-line test-example-line-odd test-example-line-1">4</div><div class="test-example-line test-example-line-odd test-example-line-1">5 5 5 5</div><div class="test-example-line test-example-line-even test-example-line-2">3</div><div class="test-example-line test-example-line-even test-example-line-2">1 3 2</div><div class="test-example-line test-example-line-odd test-example-line-3">2</div><div class="test-example-line test-example-line-odd test-example-line-3">0 0</div><div class="test-example-line test-example-line-even test-example-line-4">3</div><div class="test-example-line test-example-line-even test-example-line-4">2 5 7</div><div class="test-example-line test-example-line-odd test-example-line-5">6</div><div class="test-example-line test-example-line-odd test-example-line-5">1 2 3 3 2 1</div><div class="test-example-line test-example-line-even test-example-line-6">10</div><div class="test-example-line test-example-line-even test-example-line-6">27 27 34 32 2 31 23 56 52 4</div><div class="test-example-line test-example-line-odd test-example-line-7">5</div><div class="test-example-line test-example-line-odd test-example-line-7">1822 1799 57 23 55</div><div class="test-example-line test-example-line-odd test-example-line-7"></div>

样例输出 1

2
2
0
2
4
7
4

Note

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

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