K. Squares City
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

After a long journey around the world, you found a mythic place called $$$Squares$$$ $$$City$$$. This city is special, and a little bit strange, since all the buildings have the shape of squares, and even the city itself can be seen as a squared matrix. What is even more interesting is that, after a short walk around the city, you also realised that all the buildings and the city have lengths equal to powers of two. However, even if you found all this information captivating, your mathematical skills awakened, and now you are worried if there would be a better way to build such a city. After talking to the mayor, you found out the rules that their city must respect and you were also given the chance to come up with a new idea that will be further presented to the city council.

The rules are as follows:

  1. The city must have the shape of a square of length $$$N$$$, where $$$N$$$ is given to be of form $$$2^K$$$.
  2. The buildings that you build must have the shape of squares, and their lengths must be of form $$$2^K$$$. You are free to choose which length each building should have.
  3. You are allowed to build only above the secondary diagonal of the city, since the rest of the city will be used for recreation areas for citizens.
  4. The entire area where you are allowed to build must be used (i.e. every single cell above the secondary diagonal must have a building on it).
  5. The number of buildings that you build must be minimized.

Given these rules, the city council is going to ask you $$$Q$$$ questions of form $$$N, X, Y$$$, i.e. what is the length of the building that would be built over the cell $$$(X, Y)$$$ in your optimal representation of the city, if the city has length $$$N$$$? In case that there are several answers to the question, you should answer with $$$-1$$$.

Input

The first line of the input contains $$$1 \leq Q \leq 10^5$$$, the number of queries.

The following $$$Q$$$ lines will each contain integers ($$$N, X, Y$$$) signifying a question from the city council ($$$2 \leq N \leq 2 * 10^{18}$$$, $$$N$$$ of form $$$2^K$$$, $$$1 \leq X \leq N - 1$$$, $$$1 \leq Y \leq N - X$$$).

Output

The output should contain $$$Q$$$ lines, each of them containing the answer to the question, or $$$-1$$$ if there are several answers to the question.

Example
Input
3
4 1 1
4 1 3
4 3 1
Output
2
1
1
Note

In the given examples, the length of the city is $$$4$$$, therefore the area where you are allowed to build is represented by the following matrix:

$$$1 1 1 0\\ 1 1 0 0\\ 1 0 0 0\\ 0 0 0 0$$$

The only optimal answer is to use a building of length $$$2$$$ and two buildings of length $$$1$$$ as follows: $$$ 2 2 1 0\\ 2 2 0 0\\ 1 0 0 0\\ 0 0 0 0$$$