问题描述

对于一个正整数 $X$，设 $f(X)$ 表示 $X$ 的二进制表示中出现的 $1$ 的个数。例如，$6 = 110_{(2)}$，$11 = 1011_{(2)}$，$16 = 10000_{(2)}$，因此 $f(6) = 2$，$f(11) = 3$，$f(16) = 1$。

给定一个正整数 $N$，确定是否存在一个小于或等于 $N$ 的正整数 $X$，使得 $f(X) = 3$。如果存在，找出最大的满足条件的 $X$。

有 $T$ 组测试用例需要解决。

约束条件

• $1 \leq T \leq 10^5$
• $1 \leq N \leq 10^{18}$

输入

输入以以下格式从标准输入给出，其中 $N_i$ 表示第 $i$ 组测试用例的 $N$ 的值：

$T$

$N_1$

$N_2$

$\vdots$

$N_T$

输出

输出 $T$ 行。第 $i$ 行应输出小于或等于 $N_i$ 的最大正整数 $X$，使得 $f(X) = 3$。如果不存在这样的正整数 $X$，则输出 -1。

示例输入 1

4
16
161
4
1000000000000000000

示例输出 1

14
161
-1
936748722493063168

• 对于第一组测试用例，$f(14) = 3$，$f(15) = 4$，$f(16) = 1$，因此满足条件 $X \leq 16$ 且 $f(X) = 3$ 的最大正整数 $X$ 是 $14$。
• 对于第二组测试用例，$f(161) = 3$，因此满足条件 $X \leq 161$ 且 $f(X) = 3$ 的最大正整数 $X$ 是 $161$。
• 对于第三组测试用例，$f(1) = 1$，$f(2) = 1$，$f(3) = 2$，$f(4) = 1$，因此不存在满足条件 $X \leq 4$ 且 $f(X) = 3$ 的正整数 $X$。
• 正如第四组测试用例所示，输入和输出的值可能不适合32位整数类型。