← 返回题目列表

Codeforces · 2074/C

C. 异或和三角形

中文机器翻译题面 查看原题

这次,粉红士兵给了你一个整数$$$x$$$ ($$$x \ge 2$$$)。

请确定是否存在 积极 满足以下条件的整数 $$$y$$$。

  • $$$y$$$ 是 严格 小于 $$$x$$$。
  • 存在一个 非退化三角形$$$^{\text{*}}$$$,边长为 $$$x$$$、$$$y$$$、$$$x \oplus y$$$。这里,$$$\oplus$$$表示按位异或运算。

另外,如果存在这样的整数$$$y$$$,则输出any。

$$$^{\text{*}}$$$当 $$$a+b \gt c$$$、$$$a+c \gt b$$$、$$$b+c \gt a$$$ 时,边长为 $$$a$$$、$$$b$$$、$$$c$$$ 的三角形是非退化的。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 2000$$$)。测试用例的描述如下。

每个测试用例的唯一行包含一个整数 $$$x$$$ ($$$2 \le x \le 10^9$$$)。

输出

对于每个测试用例,在单独的行上打印一个整数。您必须输出的整数如下:

  • 如果存在满足条件的整数$$$y$$$,则输出$$$y$$$的值($$$1 \le y \lt 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$$$。