L. Greedy World
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given a sequence containing $$$k - 1$$$ $$$x$$$'s and 1 $$$y$$$. In one operation, Xiao T can take two numbers $$$a$$$ and $$$b$$$ from this sequence, and then put back two $$$\lfloor \frac{a+b}{2} \rfloor$$$. Xiao T can perform operations infinitely until all numbers in the sequence are the same. Let all numbers in the sequence be $$$S$$$, and find the minimum value of $$$S$$$.

  • $$$\lfloor x \rfloor$$$ denotes the largest integer not exceeding $$$x$$$, for example, $$$\lfloor 4 \rfloor = 4$$$, $$$\lfloor 1.2 \rfloor = 1$$$, $$$\lfloor -2.5 \rfloor = -3$$$.
Input

The input contains multiple groups of data.

First, there is a line with an integer $$$T(1 \leq T \leq 10^5)$$$, indicating the number of data groups.

For each group of data, there is a line with three integers $$$k,x,y$$$ $$$(2 \leq k \leq 10^9,$$$ $$$0 \leq x \leq 10^9,$$$ $$$ 0\leq y \leq 10^{18}, $$$ $$$0 \leq y - x \leq 2^k - 1)$$$. The meanings are as described in the problem statement.

Output

For each group of data, output a line with an integer, indicating the minimum value of $$$S$$$.

Example
Input
1
3 3 5
Output
3
Note

In the first group of data, we can first take out $$$3$$$ and $$$5$$$, because $$$\lfloor \frac{3+5}{2} \rfloor= 4$$$, so we put back $$$4$$$ and $$$4$$$. After the first round of operations, the sequence becomes $$$\{3,4,4\}$$$. Next, we take out $$$3$$$ and $$$4$$$, because $$$\lfloor \frac{3+4}{2} \rfloor = 3$$$, so we put back $$$3$$$ and $$$3$$$. After the first round of operations, the sequence becomes $$$\{3,3,4\}$$$. Finally, we take out $$$3$$$ and $$$4$$$ and put back $$$3$$$ and $$$3$$$. All numbers in the sequence are $$$3$$$. It can be proven that this method of operation can make $$$S$$$ reach the minimum value.