AT_arc220_e.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$.

给定正整数 $N,C,K$。

求满足 $\displaystyle\min_{0\le i < N} \text{popcount}(X+Ci) \geq K$ 的最小正整数 $X$。

可以证明，这样的正整数 $X$ 总是存在的。

你将得到 $T$ 组测试数据；请对每组数据求解。

什么是 popcount？

对于非负整数 $x$，$\operatorname{popcount}(x)$ 表示 $x$ 的二进制表示中 $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$ 的二进制表示为 1101，因此 $\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$

输入从标准输入中按以下格式给出：

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

每个测试用例按以下格式给出：

$N$ $C$ $K$

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

按顺序输出测试用例的答案，答案之间用换行符分隔。

Sample 1 Explanation:
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.

样例 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$ 更小的正整数满足该条件，因此第一行输出 $13$。

约束条件

• $1\le T \le 10^5$
• $1\le N\le 10^8$
• $1\le C\le 30$
• $1\le K\le 30$
• 所有输入值均为整数。