AT_arc220_e [ARC220E] popcount ≥ K

给定正整数 $N, C, K$。 请找到最小的正整数 $X$，使得对于所有 $0 \leq i < N$，都有 $\min_{0\le i < N} \operatorname{popcount}(X + Ci) \geq K$。 可以证明，总存在这样的正整数 $X$。 共有 $T$ 组测试用例，请分别求解每组。 什么是 popcount？对于非负整数 $x$，$\operatorname{popcount}(x)$ 是 $x$ 的二进制表示中 $1$ 的个数。更形式化地说，若非负整数 $x$ 满足 $x=\sum_{i=0}^{\infty} b_i 2^i \quad (b_i \in \lbrace 0,1 \rbrace)$，则有 $\operatorname{popcount}(x)=\sum_{i=0}^{\infty} b_i$。 例如，$13$ 的二进制为 `1101`，因此 $\operatorname{popcount}(13) = 3$。

输入由标准输入给出，格式如下： $T$ $\text{case}_1$ $\text{case}_2$ $\vdots$ $\text{case}_T$ 每组测试数据格式如下： $N\ C\ K$

请输出每组测试数据的答案，按顺序输出，每组一行。

### 样例解释 1 考虑第一组测试。 $X=13$ 满足条件，具体如下： - 当 $i=0$ 时，$\operatorname{popcount}(X+Ci)=\operatorname{popcount}(13)=3$； - 当 $i=1$ 时，$\operatorname{popcount}(X+Ci)=\operatorname{popcount}(14)=3$； - 当 $i=2$ 时，$\operatorname{popcount}(X+Ci)=\operatorname{popcount}(15)=4$。 不存在比 $13$ 更小的正整数满足条件，所以第一行输出 $13$。 ### 数据范围 - $1\le T \le 10^5$ - $1\le N\le 10^8$ - $1\le C\le 30$ - $1\le K\le 30$ - 所有输入数值均为整数。 由 ChatGPT 5 翻译