Largest XOR sum subarray

Interview

Time limit10sMemory limit512 MB

Summary

Given a sequence, find the maximum XOR value over all contiguous subarrays of length at least one.

Level: Medium7 of 10
Topics: Bit manipulation, Trie, Prefix sum, Array
Solved: No attempts yet

Problem

You are given a sequence $A$ of $N$ numbers. Pick one contiguous subarray of it. The XOR sum of a subarray is the value you get by XOR-ing every element in that subarray.

Given $A$ , write a program that finds the largest XOR sum over all contiguous subarrays of length at least 1.

Input

The first line contains the number of test cases $T$ . ( $1 \le T \le 10$ )

Each test case takes two lines. The first line contains the size of the sequence $N$ ( $1 \le N \le 100\,000$ ), and the second line contains the $N$ elements of $A$ separated by spaces. Each element is a non-negative integer that fits in a 32-bit signed integer, so it is an integer between $0$ and $2^{31}-1$ .

Output

For each test case, print the largest XOR sum over the contiguous subarrays of $A$ on its own line.

Examples8

Example 1
Input
```
2
5
3 7 7 7 0
5
3 8 2 6 4
```
Expected output
```
7
15
```
Example 2
Input
```
1
1
0
```
Expected output
```
0
```
Example 3
Input
```
1
1
2147483647
```
Expected output
```
2147483647
```
Example 4
Input
```
1
6
0 0 0 0 0 0
```
Expected output
```
0
```
Example 5
Input
```
1
2
5 5
```
Expected output
```
5
```
Example 6
Input
```
1
6
8 1 2 15 0 8
```
Expected output
```
15
```
Example 7
Input
```
1
2
1073741824 1073741823
```
Expected output
```
2147483647
```

Example 8

Input

3
4
1 2 4 8
3
2147483647 2147483647 2147483647
1
1

Expected output

15
2147483647
1