На шельфе ведётся разработка нового морского месторождения. Инженеры выбирают две скважины для совместной работы: основную и вспомогательную.

Для очередного участка уже известен параметр основной скважины x. Нужно подобрать параметр вспомогательной скважины y, где 1 <= y < x.

После выбора двух скважин система автоматически вычисляет ещё один служебный параметр:

z = x xor y

Тройка параметров (x, y, z) считается устойчивой конфигурацией, если из этих трёх чисел можно составить невырожденный треугольник. Иными словами, одновременно должны выполняться условия:

• x + y > z
• x + z > y
• y + z > x

Для каждого заданного x найдите любое подходящее значение y.

Если такого значения не существует, выведите -1.

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

В первой строке записано одно целое число t — количество наборов входных данных.

В каждой из следующих t строк записано одно целое число x (2 <= x <= 10^9) — параметр основной скважины.

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

Для каждого набора данных выведите одно целое число:

• любое число y, такое что 1 <= y < x и числа x, y, x xor y образуют невырожденный треугольник;
• -1, если подходящего значения не существует.

Если существует несколько ответов, разрешается вывести любой из них.

Пример

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

7
5
2
6
3
69
4
420

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

3
-1
5
-1
66
-1
320

Пояснение

Рассмотрим первый набор: x = 5, можно выбрать y = 3.

Тогда:

• z = 5 xor 3 = 6
• получаем числа 5, 3 и 6

• они образуют невырожденный треугольник, так как:

  • 5 + 3 > 6
  • 5 + 6 > 3
  • 3 + 6 > 5