← 返回题目列表

Codeforces · 1635/A

A. 最小值或总和

中文机器翻译题面 查看原题

给定一个数组 $$$a$$$,大小为 $$$n$$$。

您可以对阵列执行以下操作:

- 选择两个不同的整数 $$$i, j$$$ $$$(1 \leq i < j \leq n$$$),用 $$$x$$$ 替换 $$$a_i$$$,用 $$$y$$$ 替换 $$$a_j$$$。为了不破坏数组,$$$a_i | a_j = x |必须保留 y$$$,其中 $$$|$$$ 表示按位或运算。请注意,$$$x$$$ 和 $$$y$$$ 是非负整数。

请输出使用上述操作任意次数后得到的数组的最小和。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ $$$(1 \leq t \leq 1000)$$$。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ $$$(2 \leq n \leq 100)$$$ — 数组 $$$a$$$ 的大小。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots ,a_n$$$ $$$(0 \leq a_i < 2^{30})$$$。

输出

对于每个测试用例,在一行中打印一个数字 - 数组的最小可能总和。

示例

输入 #1

4
3
1 3 2
5
1 2 4 8 16
2
6 6
3
3 5 6

输出 #1

3
31
6
7

注意

在第一个示例中,可以通过以下操作获取数组$$$[1, 0, 2]$$$:

1. 选择$$$i = 1, j = 2$$$,更改$$$a_1 = 1$$$ 和$$$a_2 = 2$$$,从$$$1 | 开始有效3 = 1 | 2$$$。该数组变为 $$$[1, 2, 2]$$$。

2. 选择$$$i = 2, j = 3$$$,更改$$$a_2 = 0$$$ 和$$$a_3 = 2$$$,自$$$2起有效 | 2 = 0 | 2$$$。该数组变为 $$$[1, 0, 2]$$$。

我们可以证明最小和是 $$$1 + 0 + 2 = 3$$$

在第二个示例中,我们不需要任何操作。