Largest XOR sum subarray

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

Medium7Bit manipulationTriePrefix sumArrayInterviewNo attempts yetTime limit10sMemory limit512 MB

Problem

You are given a sequence AA of NN 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 AA, 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 TT. (1T101 \le T \le 10)

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

Output

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