J. [ARC161B] Exactly Three Bits

传统题

2000ms

1024MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

AT_arc161_b [ARC161B] Exactly Three Bits

对于一个正整数 $X$ ，定义 $f(X)$ 为 $X$ 在二进制表示下 $1$ 的个数，比如，因为 $6=110_{(2)}$ ， $11=1101_{(2)}$ ， $16=10000_{(2)}$ ，所以 $f(6)=2$ ， $f(11)=3$ ， $f(16)=1$ 。

现在给定你一个正整数 $N$ ，问是否存在一个小于等于 $N$ 的正整数 $X$ ，满足 $f(X)=3$ 。如果存在，请输出满足条件的最大的 $X$ ，否则输出 -1。

本题有多组数据。

第一行一个整数 $T(1\le T\le10^5)$ ，表示数据组数。

接下来 $T$ 行每行一个正整数 $N(1\le N\le10^{18})$ 。

共 $T$ 行，每行一个整数表示第 $i$ 个问题的答案。

输入

4
16
161
4
1000000000000000000

输出

14
161
-1
936748722493063168