题目描述

对于一个正整数 $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$ 个问题的答案。

样例 1

输入

4
16
161
4
1000000000000000000

输出

14
161
-1
936748722493063168