Background

Special for beginners, ^_^

Description

给出非负整数n，求最大的不超过n的整数x，且x化成二进制恰好有三位1。

如果不存在，则输出-1。

Format

Input

第一行为一个整数T（$\le 10^5$），表示有T组数据。

后面T行，每行一个非负整数N（$\le 10^{19}$）

Output

每行输出一个答案，最大的不超过n的整数x，且x化成二进制恰好有三位1。

Samples

5
16
3
114
514
1145141919810

14
-1
112
448
1142461300736

Limitation

1s, 1024KiB for each test case.