\(7 = 111_{(2)}\) が \(f(X) = 3\) を満たす最小の正整数 \(X\) なので，\(N_i \le 6\) であれば -1 を出力します． 以下では \(N_i \ge 7\) を仮定します．

解法 1.$~~$候補全列挙

\(10^{18}\) 以下の正整数であって，\(2\) 進法表記したときに \(1 \) がちょうど \(3\) 個現れるようなものは，高々 \(\displaystyle\binom{60}{3} = 34220\) 個しかありません．（ \(10^{18} < 2^{60}\) なので，\(1\) は \(2^{59}\) の位以下の \(60\) 箇所にしか現れ得ません．） したがって，これら（ \(M\) 個とする）を素朴に \(3\) 重ループなどで全列挙してソートしておき，各テストケース \(N_i\) について二分探索で \(N_i\) 以下の最大値を求めることで，各テストケースに \(\mathrm{O}(\log M)\) 時間，全体として \(\mathrm{O}((M + T) \log M)\) 時間で答えることができます．

実装例 (C, 48 ms)

解法 2.$~~$場合分け

\(N_i\) を \(2\) 進法表記したときに，

• \(1\) が \(3\) 個以上現れるのであれば，上位から \(3\) つだけを残したものが答えです．
• \(1\) がちょうど \(1\) 個現れるのであれば，それを \(0\) にしてその直下に \(1\) を \(3\) つ連続して並べたものが答えです．
• \(1\) がちょうど \(2\) 個現れる場合，
  • 下位の \(1\) が \(2^2\) 以上の位であれば，それを \(0\) にしてその直下に \(1\) を \(2\) 個連続して並べたものが答えです．
  • 下位の \(1\) が \(2^1\) 以下の位であれば，\(1\) をともに \(0\) にして，上位の \(1\) の直下に \(1\) を \(3\) 個連続して並べたものが答えです．

いずれの場合も，上で示したものが \(N_i\) 以下の正整数であることは明らかであり，最大性に関しては数学的帰納法により証明できます．（解法 3 の正当性がほぼそのまま証明となります．） 解法としては，\(1\) の出現個数と位置を確認すればよいだけなので，各テストケースについて \(\mathrm{O}(\log N_i)\) 時間で答えることができます．

実装例 (C, 45 ms)

解法 3.$~~$再帰

\(x = N_i\) から始めて，入力が \(x\) であった場合の答えを再帰的に求めます．

• \(f(x) = 3\) であれば，\(x\) を答えとして出力する．（ \(x\) が条件を満たすので，\(x\) 以下で条件を満たす最大値は明らかに \(x\) 自身です．）
• \(f(x) < 3\) であれば，\(x\) を \(x - 1\) で置き換える．（ \(x\) が条件を満たさないので，答えは \(x - 1\) 以下の範囲にあります．）
• \(f(x) > 3\) であれば，\(x\) に現れる最下位の \(1\) を \(0\) にしたもので \(x\) を置き換える．
  正当性

  \(x\) が条件を満たさないので，答えは \(x - 1\) 以下の範囲にあります． さらに，元の \(x\) 以下かつ置き換え後の \(x\) より真に大きい任意の整数 \(y\) について，置き換えられた桁より上の状態は全く同じであり，置き換えられた桁以下に少なくとも \(1\) つの \(1\) があるため，\(f(y) > 3\) が成り立ちます． したがって，この範囲の確認は飛ばしてしまって問題ありません．

入力時と \(2\) 番目の場合の更新後以外に \(f(x)\) を真面目に計算する必要は無く，\(2\) 番目の場合の更新は高々 \(3\) 回しか起こらない（ \(2^0\) の位が \(1\) である場合を除いて \(f(x)\) は減らないし，そうでないときは \(2^1\) の位が \(1\) である場合を除いて \(f(x)\) は \(3\) 以上まで増える）ので，各テストケースについて \(\mathrm{O}(\log N_i)\) 時間で答えることができます．

実装例 (C, 50 ms)

なお，解法 2, 3 において，\(f(X)\) の計算を無駄に多くしてしまうと，各テストケースの計算量は最悪 \(\Theta((\log N_i)^2)\) になります． 高速な言語を用いたり，効率的な実装をしていたりすれば，それでも AC を得ることができます．