小苯的序列涂色

题号：NC315473
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 给定一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$ 。小苯可以进行若干次染色操作：每次选择一个区间 $[l, r] \left(1 \leqq l \leqq r \leqq n\right)$ ，将该区间内所有位置染成红色，并支付 $\textstyle\bigoplus_{i=l}^r a_i$ 的代价（即区间内所有数字的按位异或和）。
$\hspace{15pt}$ 初始时所有位置都是白色。每次操作选择的区间可以重叠，即同一位置可以被多次染色。目标是将所有位置都染成红色。

$\hspace{15pt}$ 请帮助小苯计算，将所有位置染红所需的最小总代价。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入一个整数 。
第二行输入  个整数 。

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每一组测试数据，新起一行输出一个整数，表示将所有位置染红的最小总代价。

示例1

输入

复制

输出

复制

0
1

说明

对于第一组测试数据，最优方案是染色 ，代价 。

备注:

在几乎全部的情况下，PyPy 的运行速度优于 Python，我们建议您选择对应版本的 PyPy 进行提交、而不是 Python。