A. Минимальная OR сумма
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив чисел $$$a$$$ размера $$$n$$$.

Вы можете выполнить следующую операцию над массивом:

  • Выберите два различных целых числа $$$i, j$$$ $$$(1 \leq i < j \leq n$$$), замените $$$a_i$$$ на $$$x$$$ и $$$a_j$$$ на $$$y$$$. Чтобы не нарушать массив, должно выполняться $$$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})$$$.

Выходные данные

Для каждого набора входных данных выведите в строке одно число — минимальную возможную сумму массива.

Пример
Входные данные
4
3
1 3 2
5
1 2 4 8 16
2
6 6
3
3 5 6
Выходные данные
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$$$.

Во втором примере нам не нужны никакие операции.