Problem Statement

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

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.

Input

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

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