当前没有测试数据。

题目描述

在一个神秘的数字王国中，有一位年迈的数学家，他以解决数学难题而闻名于世。他的名字是阿尔伯特。阿尔伯特一直追求着数字的奥秘，并且相信数字中蕴含着无尽的力量。

有一天，阿尔伯特发现了一种神秘的能量，被称为"二进制之力"。

根据阿尔伯特的研究，对于正整数 $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$ 个测试案例，每个测试案例都是一次数字之旅。

输入

第一行读入数据组数 $T$。

下面的 $T$ 行，每一行给出一个整数 $N$。

输出

输出 $T$ 行对应的满足条件的最大 $X$。

如果不存在这样的正整数，就输出 -1。

样例

输入复制

4
16
161
4
1000000000000000000

输出复制

14
161
-1
936748722493063168

输入复制

1
100

输出复制

100

说明

【样例 $1$ 解释】

$T = 4$，有$4$组数据：

$16$，小于等于 $16$ 的满足条件最大值 $14$，二进制：$1110$。

$161$ ，小于等于 $161$ 的满足条件最大值 $161$，二进制：$10100001$。

$4$ ，小于等于 $4$ 的满足条件最大值不存在，所以输出 $-1$。

$1000000000000000000$ ，小于等于 $16$ 的满足条件最大值 $936748722493063168$。

其二进制结果为： $110100000000000000000000000000000000000000000000000000000000$。

【样例 $2$ 解释】

$T = 1$，有$1$ 组数据：

$N = 100$ 对应的二进制：$1100100$ ,有 $3$ 个$1$，小于等于 $100$ 的最大的就是 $100$，输出 $100$。

【数据范围】

对于 30% 的数据,$1≤T≤10^2,1≤N≤10^6$。

对于 60% 的数据,$1≤T≤10^5,1≤N≤10^9$。

对于 100% 的数据,$1≤T≤10^5,1≤N≤10^{18}$。