G. Коллекция красивых простых чисел
ограничение по времени на тест
5 с
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана колода из $$$n$$$ карт, на каждой из которых записано число $$$a_i$$$. Игра начинается с пустой руки и начального общего счета, равного нулю.

На $$$i$$$-м ходу вы должны взять $$$i$$$-ю карту со значением $$$a_i$$$, затем по желанию сбросить некоторые карты из вашей руки, обеспечив, чтобы после этого шага побитовое исключающее ИЛИ любых двух оставшихся карт в руке было простым числом. Счёт за этот ход — это сумма значений всех карт в вашей руке, которая затем добавляется к общему счету.

Определите максимальный возможный общий счет после завершения всех $$$n$$$ ходов.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 50$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 150$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \lt 2^{20}$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$150$$$.

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

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

Пример
Входные данные
3
5
1 2 3 4 5
9
9 9 8 2 4 4 3 5 3
2
323468 765165
Выходные данные
24 
103 
1412101
Примечание

Карты, взятые на соответствующих ходах, выделены красным, в то время как сброшенные карты зачеркнуты.

В первом наборе входных данных вы можете сыграть с начальной пустой рукой $$$\{\}$$$ и счётом $$$0$$$ следующим образом:

  • после завершения первого хода: $$$\{\color{red}{1}\}$$$ $$$\overset{\text{последующее удаление}}{\xrightarrow{\hspace{1.3cm}}}$$$ $$$\{1\}$$$ и общий счет $$$0 + 1 = 1$$$;
  • после завершения второго хода: $$$\{1, \color{red}{2}\}$$$ $$$\overset{\text{последующее удаление}}{\xrightarrow{\hspace{1.3cm}}}$$$ $$$\{1, 2\}$$$ и общий счет $$$1 + 3 = 4$$$;
  • после завершения третьего хода: $$$\{1, \not{2}, \color{red}{3}\}$$$ $$$\overset{\text{последующее удаление}}{\xrightarrow{\hspace{1.3cm}}}$$$ $$$\{1, 3\}$$$ и общий счет $$$4 + 4 = 8$$$. Обратите внимание, что карты со значениями $$$2$$$ и $$$3$$$ не могут находиться в руке одновременно, так как $$$2 \oplus 3 = 1$$$, что не является простым числом. Чтобы решить эту проблему, мы можем сбросить карту со значением $$$2$$$;
  • после завершения четвертого хода: $$$\{1, 3, \color{red}{4}\}$$$ $$$\overset{\text{последующее удаление}}{\xrightarrow{\hspace{1.3cm}}}$$$ $$$\{1, 3, 4\}$$$ и общий счет $$$8 + 8 = 16$$$;
  • после завершения пятого хода: $$$\{1, 3, 4, \not{\color{red}{5}}\}$$$ $$$\overset{\text{последующее удаление}}{\xrightarrow{\hspace{1.3cm}}}$$$ $$$\{1, 3, 4\}$$$ и общий счет $$$16 + 8 = 24$$$.