[Solution] Burenka and Traditions (hard version) solution codeforces

Burenka and Traditions (hard version) solution codeforces – 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.

Table of Contents

Burenka and Traditions (hard version) solution codeforces

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𝑙𝑟𝑛1≤l≤r≤n and a non-negative integer 𝑥x, then
  • for all 𝑙𝑖𝑟l≤i≤r assign 𝑎𝑖:=𝑎𝑖𝑥ai:=ai⊕x, where  denotes the bitwise XOR operation. It takes 𝑟𝑙+12⌈r−l+12⌉ seconds to do this operation, where 𝑦⌈y⌉ 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𝑡500)(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𝑛105)(1≤n≤105) – the size of the array

The second line of each test case contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,⋯,an (0𝑎𝑖<230)(0≤ai<230) — elements of the array.

It is guaranteed that the sum of 𝑛n in all tests does not exceed 105105.

Burenka and Traditions (hard version) solution codeforces

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

Example
input

Copy
7
4
5 5 5 5
3
1 3 2
2
0 0
3
2 5 7
6
1 2 3 3 2 1
10
27 27 34 32 2 31 23 56 52 4
5
1822 1799 57 23 55
output

Copy
2
2
0
2
4
7
4

Burenka and Traditions (hard version) solution codeforces

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

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

For Solution

“Click Here”

Leave a Comment