Universal Cup Judging System

Universal Cup

実行時間制限: 1.0 s メモリ制限: 512 MB 満点: 100 ハック可能 ✓
統計

У Нуара есть $n$ самоцветов. На $i$-м самоцвете написано положительное целое число $a_i$. Нуар хочет разделить эти самоцветы на несколько непустых групп. Каждый самоцвет должен принадлежать ровно одной группе.

Предположим, что $i$-я группа содержит самоцветы с номерами $k_{i,1}, k_{i,2}, \dots, k_{i,p}$; тогда Нуар считает яркостью $i$-й группы величину $a_{k_{i,1}} \oplus a_{k_{i,2}} \oplus \cdots \oplus a_{k_{i,p}}$, где $\oplus$ — операция побитового исключающего ИЛИ (XOR). Обозначим яркость $i$-й группы через $B_i$.

Для способа разбиения на $m$ групп Нуар считает ценностью этого способа величину $B_1 \& B_2 \& \dots \& B_m$, где $\&$ — операция побитового И (AND).

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

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

Входные данные состоят из нескольких наборов входных данных. Первая строка входных данных содержит целое число $T$ ($1 \le T \le 10^4$) — количество наборов входных данных.

Для каждого набора входных данных первая строка содержит целое число $n$ ($1 \le n \le 5 \times 10^5$) — количество самоцветов.

Вторая строка содержит $n$ целых чисел $a_1, a_2, \cdots, a_n$ ($1 \le a_i < 2^{60}$) — числа, написанные на самоцветах.

Гарантируется, что сумма $n$ по всем наборам входных данных не превосходит $5 \times 10^5$.

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

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

Пример

4
4
1 2 3 1
6
4 7 5 2 6 3
4
14 15 9 18
2
251508091405 13011908091815
2
6
26
13121614001578

Примечание

В первом наборе входных данных один из возможных способов разбиения — $[1, 2, 3, 1] = [1, 3], [2, 1]$ с ценностью $B_1 \& B_2 = (1 \oplus 3) \& (2 \oplus 1) = 2 \& 3 = 2$. Другой возможный способ разбиения — $[1, 2, 3, 1] = [1, 2, 3, 1]$ с меньшей ценностью $B_1 = 1 \oplus 2 \oplus 3 \oplus 1 = 1$. Можно доказать, что получить ценность больше $2$ невозможно.

Во втором наборе входных данных наилучший способ разбиения — $[4, 7, 5, 2, 6, 3] = [7], [5, 3], [6], [4, 2]$ с ценностью $7 \& (5 \oplus 3) \& 6 \& (4 \oplus 2) = 6$.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.