D. 有损变换
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

对于非负整数 $$$x$$$，我们定义 or-shift 变换 $$$f(x)$$$ 为 $$$x$$$ 和 $$$2 x$$$ 的按位或$$$^{\text{∗}}$$$，即： $$$$$$ f(x) = x \mathbin{|} (2 x) $$$$$$

给定一个非负整数 $$$y$$$，请你判断是否存在一个非负整数 $$$x$$$，使得 $$$f(x) = y$$$。

如果存在，输出任意一个满足要求的 $$$x$$$；否则，输出 $$$-1$$$。

$$$^{\text{∗}}$$$按位或（bitwise OR）是一种二进制按位运算，记作 $$$a \mathbin{|} b$$$。它对两个无符号整数对应二进制位分别进行逻辑或运算：若某一位上至少有一个数位为 $$$1$$$，则结果的该位为 $$$1$$$；否则为 $$$0$$$。例如 $$$ 5 \mathbin{|} 3 =(0101)_2 \mathbin{|} (0011)_2 =(0111)_2 =7 $$$。

Input

本题的输入包含多组测试用例。

第一行一个整数 $$$T$$$（$$$1 \leq T \leq 10^4$$$），表示测试用例的数量。对于每组测试用例：

  • 仅一行，包含一个非负整数 $$$y$$$（$$$0 \leq y \lt 2^{60}$$$）。
Output

对于每组测试用例：

  • 如果存在满足要求的 $$$x$$$，输出一行，包含一个非负整数 $$$x$$$；
  • 否则，输出 $$$-1$$$。

如果存在多个满足要求的 $$$x$$$，你可以输出其中任意一个。

Example
Input
8
0
15
1918
1919
15747
114514
4286561280
1152921504606846975
Output
0
5
810
811
7297
-1
2000000000
576460752303423487