题面描述

游游有一个长度为 $n$ 的数组 $a$。定义两个函数：

• $f(a)=a_1+a_2+\dots+a_m$（数组所有元素之和，其中 $m$ 为数组长度）；
• $g(a)=a_1\mid a_2\mid\dots\mid a_m$（数组所有元素的按位或）。
  现将数组 $a$ 恰好分割成两个非空数组 $b$ 和 $c$，要求最小化

思路

题目内容

你有一个长度为 $n$ 的数组 $a$ ，游游定义了两个数组上的函数： $- f(a) = a_1 + a_2 + … + a_m$ （即数组中所有数字的和，其中 $m$ 为数组长度）； $- g(a) = a_1 | a_2 | … | a_m$ （即数组中所有数字的按位或值）。 现在，游游希望你将 $a$ 分割成恰好两个非空的数组 $b$ 和 $c$ ，以最小化 $|f(b) - g(c)|$的值。

输入描述

本题有多组测试数据。 输入的第一行包含一个正整数 $T (1 ≤ T ≤ 100)$，表示数据组数。接下来包含 $T$ 组数据，每组数据的格式如下： 第一行一个正整数 $n (2 ≤ n ≤ 2×10^5)$ ，表示数组 $a$ 的长度； 第二行 $n$ 个整数 $a_i (0 ≤ a_i ≤ 10^9)$ ，表示数组 $a$ 。（保证所有测试数据中，$n$ 的总和不超过 $2×10^6$ ）

输出描述

输出一个值表示你选择并调整后的六面骰顶部值的和与 $m$ 的绝对值。

样例1

输入

1
5
1 2 3 4 5

输出

1

说明

将 $a$ 切割为：$b =${$1, 2, 3$}, $c =${$4, 5$}。此时 $f(b) = 1 + 2 + 3 = 6$, $g(c) = 4 | 5 = 7$。因此所求为 $1$ 最小。可以证明不存在更小的答案。