XOR 목걸이

Frograms, Inc.는 새로운 디자인과 기능을 갖춘 목걸이를 개발해 왔다. 이 회사의 프로그래머는 모두 이 목걸이를 착용한다. 목걸이는 실에 꿴 여러 개의 구슬로 이루어진다. 각 구슬에는 0 이상 10^9 이하의 정수가 적혀 있다.

여름휴가로 대부분의 프로그래머가 자리를 비워서 오늘 사무실에는 몇 명만 남아 있다. 그들은 목걸이로 게임을 해서 점심을 누가 살지 정하기로 했다. 연속한 두 구슬마다 두 수의 합을 구한다. 프로그래머의 점수는 이 합들을 모두 XOR($\oplus$)한 값이다. 점수가 가장 낮은 프로그래머가 진다.

목걸이를 둘러싼 순서대로 구슬의 값이 $A\_1$, $A\_2$, $\cdots$, $A\_N$이면 점수는 다음과 같다.

$(A\_1 \oplus A\_2) + (A\_2 \oplus A\_3) + \dots + (A\_{N-1} \oplus A\_N) + (A\_N \oplus A\_1)$

너는 구슬을 0개 이상 제거해서 점수를 최대로 만들 수 있다. 구슬의 순서는 바꿀 수 없고, 목걸이에는 구슬이 최소 두 개 남아 있어야 한다. 구슬 일부를 제거했을 때 얻을 수 있는 최대 점수는 얼마인가?

입력은 $T$개의 테스트 케이스로 이루어진다. 첫 줄에 $T$가 주어진다.

각 테스트 케이스는 구슬의 개수 $N$ ($2 \le N \le 500$)을 담은 한 줄로 시작한다. 다음 줄에는 공백으로 구분된 정수 $N$개 $A\_1$, $A\_2$, $\cdots$, $A\_N$이 주어진다.

각 테스트 케이스마다 얻을 수 있는 최대 점수를 한 줄에 출력한다.