分数: 400 点
问题陈述
对于正整数 X,让 f(X) 是数量 1出现时 X 以二进制表示。 例如, 6 = 110_{(2)}, \ 11 = 1011_{(2)}, \ 16 = 10000_{(2)},所以 f(6) = 2, \ f(11) = 3, \ f(16) = 1.
给你一个正整数 N。 判断是否存在正整数 X 小于或等于 N 这样 f(X) = 3,如果是的话,找到这样的最大值 X.
有 T 测试用例解决。
约束
- 1 \leq T \leq 10^5
- 1 \leq N \leq 10^{18}
输入
输入由标准输入按以下格式给出,其中 N_i 代表的值 N 在 i-第一个测试用例:
T N_1 N_2 \vdots N_T
输出
打印 T 行。
的 i- 第行应包含最大正整数 X 小于或等于 N_i 这样 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 满意 X \leq 16 和 f(X) = 3 is 14.
- 对于第二个测试用例, f(161) = 3,所以最大正整数 X 满意 X \leq 161 和 f(X) = 3 is 161.
- 对于第三个测试用例, f(1) = 1, \ f(2) = 1, \ f(3) = 2, \ f(4) = 1,所以没有正整数 X 满意 X \leq 4 和 f(X) = 3.
- 如第四个测试用例所示,输入和输出值可能不适合 32 位整数类型。