AT_arc220_e [ARC220E] popcount ≥ K

正整数 $ N,C,K $ が与えられます。 $ \displaystyle\min_{0\le i < N} \text{popcount}(X+Ci) \geq K $ を満たす最小の正整数 $ X $ を求めてください。 ただし、そのような正整数 $ X $ は必ず存在することが証明できます。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。 popcount とは？非負整数 $ x $ について $ \operatorname{popcount}(x) $ とは、 $ x $ を $ 2 $ 進法で表記したときの $ 1 $ の個数です。 より厳密には、非負整数 $ x $ について $ \displaystyle x=\sum _ {i=0} ^ \infty b _ i2 ^ i\ (b _ i\in\lbrace0,1\rbrace) $ が成り立っているとき $ \displaystyle\operatorname{popcount}(x)=\sum _ {i=0} ^ \infty b _ i $ です。 例えば、 $ 13 $ を $ 2 $ 進法で表記すると `1101` なので、 $ \operatorname{popcount}(13)=3 $ となります。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ C $ $ K $

各テストケースに対する答えを順に改行区切りで出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースについて考えます。 $ X=13 $ は - $ i=0 $ のとき： $ \text{popcount}(X+Ci)=\text{popcount}(13)=3 $ - $ i=1 $ のとき： $ \text{popcount}(X+Ci)=\text{popcount}(14)=3 $ - $ i=2 $ のとき： $ \text{popcount}(X+Ci)=\text{popcount}(15)=4 $ より条件を満たしていることが確認できます。 $ 13 $ より小さい条件を満たす正整数は存在しないので、 $ 1 $ 行目には $ 13 $ を出力してください。 ### Constraints - $ 1\le T \le 10^5 $ - $ 1\le N\le 10^8 $ - $ 1\le C\le 30 $ - $ 1\le K\le 30 $ - 入力される値は全て整数