← 返回题目列表

AtCoder · arc161_b

B. 正好三位

中文机器翻译题面 查看原题

分数: 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 位整数类型。