题目描述

一条观测带被划分为 $n$ 个连续格点，第 $i$ 个格点记录着一个非负整数 $a_i$。

你可以多次选择一个连续区间 $[l,r]$，把该区间里的所有格点标记为已覆盖。一次选择的代价为 $a_l\oplus a_{l+1}\oplus\cdots\oplus a_r$，其中 $\oplus$ 表示按位异或。

同一个格点允许被不同的区间重复覆盖。你的目标是让所有 $n$ 个格点都至少被覆盖一次，并使总代价尽可能小。

请对每组数据求出这个最小总代价。

输入格式

第一行输入一个整数 $T$，表示测试数据组数。

对于每组数据，第一行输入一个整数 $n$。

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

对于每组数据，输出一行一个整数，表示覆盖所有格点的最小总代价。

样例

3
3
1 4 1
4
1 2 3 0
6
8 1 9 1 8 7

4
0
6

样例说明

数据范围

• 对于 $50\%$ 的数据，单个测试文件中所有测试数据的 $n$ 之和不超过 $500$。
• 对于 $100\%$ 的数据，$1\le T\le 100$，$1\le n\le 5\times 10^3$，$0\le a_i\le 10^9$。

保证单个测试文件中所有测试数据的 $n$ 之和不超过 $5\times 10^3$。