AT_arc220_e [ARC220E] popcount ≥ K

You are given positive integers $ N,C,K $ . Find the smallest positive integer $ X $ satisfying $ \displaystyle\min_{0\le i < N} \text{popcount}(X+Ci) \geq K $ . It can be proved that such a positive integer $ X $ always exists. You are given $ T $ test cases; solve each of them. What is popcount?For a non-negative integer $ x $ , $ \operatorname{popcount}(x) $ is the number of $ 1 $ s in the binary representation of $ x $ . More formally, for a non-negative integer $ x $ satisfying $ \displaystyle x=\sum _ {i=0} ^ \infty b _ i2 ^ i\ (b _ i\in\lbrace0,1\rbrace) $ , we have $ \displaystyle\operatorname{popcount}(x)=\sum _ {i=0} ^ \infty b _ i $ . For example, $ 13 $ in binary is `1101`, so we have $ \operatorname{popcount}(13)=3 $ .

The input is given from Standard Input in the following format: > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ Each test case is given in the following format: > $ N $ $ C $ $ K $

Output the answers for the test cases in order, separated by newlines.

### Sample Explanation 1 Consider the first test case. $ X=13 $ satisfies the condition, as confirmed below: - When $ i=0 $ : $ \text{popcount}(X+Ci)=\text{popcount}(13)=3 $ - When $ i=1 $ : $ \text{popcount}(X+Ci)=\text{popcount}(14)=3 $ - When $ i=2 $ : $ \text{popcount}(X+Ci)=\text{popcount}(15)=4 $ There is no positive integer smaller than $ 13 $ satisfying the condition, so output $ 13 $ on the first line. ### Constraints - $ 1\le T \le 10^5 $ - $ 1\le N\le 10^8 $ - $ 1\le C\le 30 $ - $ 1\le K\le 30 $ - All input values are integers.