XOR Necklace

문제 정보


Frograms, Inc. has been busy developing necklaces with brand-new design and feature. Every programmer working at Frograms now wears this necklace. A necklace consists of multiple beads stringed by a thread, as seen below. Each bead is given a number between 0 to 109 (inclusive).

Most of the programmers have left for their summer vacation, and there is only a few programmers in the office today. So they decided to play a game using their own necklace to decide who will buy lunch for everyone. The rule is simple: for each pair of consecutive beads in the necklace, we take the XOR of their numbers. A programmer's score is defined as the sum of all those XOR values. The programmer with the lowest score loses! More formally, if there are N beads and their value is denoted by A1, A2, ..., AN in the order they are stringed together, then the score is:

(A1 xor A2) + (A2 xor A3) + ... + (AN-1 xor AN) + (AN xor A1)

However, you, the most talented programmer in Frograms, Inc., is going to cheat the game by removing zero or more beads to maximize the score. What is the maximum score if you are allowed to remove some of the beads in a given necklace? Note that you cannot reorder the beads, nor leave one or less beads in a necklace.


The input consists of T test cases. The first line of the input contains T.

Each test case starts with a line containing a single integer N (2 <= N <= 500), the number of beads on your necklace. The next line contains N integers A1, A2, ..., AN, separated by a single space.


For each test case, print the maximum score possible you can get in a single line.

예제 입력

2 31 23 27 10 20

예제 출력



  • 출제: wookayin
  • 디스크립션: Being
  • 데이터 준비: wookayin
  • 검수: Being

3개의 댓글이 있습니다.