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

На этот раз розовые солдаты дали вам целое число $$$x$$$ ($$$x \ge 2$$$).

Пожалуйста, определите, существует ли положительное целое число $$$y$$$, которое удовлетворяет следующим условиям.

  • $$$y$$$ строго меньше $$$x$$$.
  • Существует невырожденный треугольник$$$^{\text{∗}}$$$ со сторонами длиной $$$x$$$, $$$y$$$, $$$x \oplus y$$$. Здесь $$$\oplus$$$ обозначает побитовую операцию XOR.

Кроме того, если существует такое целое число $$$y$$$, выведите любое.

$$$^{\text{∗}}$$$Треугольник со сторонами длиной $$$a$$$, $$$b$$$, $$$c$$$ является невырожденным, если $$$a+b > c$$$, $$$a+c > b$$$, $$$b+c > a$$$.

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

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

Единственная строка каждого набора содержит одно целое число $$$x$$$ ($$$2 \le x \le 10^9$$$).

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

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

  • Если существует целое число $$$y$$$, удовлетворяющее условиям, выведите значение $$$y$$$ ($$$1 \le y < x$$$);
  • В противном случае выведите $$$-1$$$.

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

Пример
Входные данные
7
5
2
6
3
69
4
420
Выходные данные
3
-1
5
-1
66
-1
320
Примечание

В первом примере существует невырожденный треугольник со сторонами длины $$$3$$$, $$$5$$$ и $$$3 \oplus 5 = 6$$$. Поэтому $$$y=3$$$ является допустимым ответом.

Во втором примере $$$1$$$ является единственным возможным кандидатом для $$$y$$$, но он не может образовать невырожденный треугольник. Поэтому ответ $$$-1$$$.