406796: GYM102558 C Программист на пляже

Memory Limit:0 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. Программист на пляжеограничение по времени на тест2 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Однажды программист Алексей из Яндекса взял отпуск и уехал отдыхать на море. В один из дней он пошёл на пляж, причём пошёл туда не один. Возможно, он пошёл туда с мамой, возможно, с бабушкой, а, возможно, с другом или подругой. Важно, что пошёл он туда не один.

На пляже программист Алексей обнаружил, что осталось всего $$$n$$$ ($$$2 \leq n \leq 10^6$$$) свободных лежаков. Но среди всего этого множества лежаков программисту Алексею нужно было всего лишь 2: для него самого и для того (или той), с кем он пришёл. Так как программист Алексей очень любил порядок, то он хотел, чтобы лежаки были как можно более похожи друг на друга. Похожесть лежаков можно вычислить следующим образом:

  • Каждому лежаку каким-то образом по его внешним признакам назначается некоторое число $$$a_i$$$ ($$$1 \leq i \leq n$$$, $$$0 \leq a_i \leq 10^9$$$).
  • Затем непохожесть двух лежаков вычисляется как XOR (побитовое исключающее ИЛИ) чисел назначенных этим лежакам. Чем значение непохожести меньше, тем более похожи лежаки.

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

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

В первой строке задано число $$$T$$$ ($$$1 \leq T \leq 1000$$$) – количество тестов. Каждый тест состоит из двух строк.

В первой строке каждого теста задано число $$$n$$$ ($$$2 \leq n \leq 10^6$$$) – количество лежаков.

Во второй строке каждого теста заданы $$$n$$$ чисел $$$a_i$$$ ($$$1 \leq i \leq n$$$, $$$0 \leq a_i \leq 10^9$$$) – значения, которые были поставлены лежакам в соответствие по внешним признакам.

Сумма $$$n$$$ по всем тестам не превосходит $$$10^6$$$.

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

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

ПримерыВходные данные
1
5
1 2 4 8 16
Выходные данные
3
Входные данные
2
2
2 4
4
2 4 6 8
Выходные данные
6
2
Примечание

В первом примере Алексей выберет лежаки со значениями 1 и 2.

В первой части второго примера Алексей может взять только лежаки со значениями 2 и 4. Во второй части он выберет лежаки со значениями 4 и 6.

加入题单

上一题 下一题 算法标签: