As the Supreme Overdeity of Informatics of the William Collegiate Institute, Allan has now been selected to give a lesson on bitmasks and their operations. While he was creating his lesson plan, he came up with the following question:

You're given the numbers and queries . For each query , he wants you to find the minimum number of operations to transform it from to any integer in the range (or if it's impossible). A single operation is defined as inserting a

`0`

or`1`

at any position in the binary representation of an integer.Here are some examples (note that the digit in square brackets is the newly inserted one):

`100 -> 10[1]0`

:`100 -> [1]100`

:`100 -> 100[1]`

:

Important note: leading s are not counted.

As you want to prove to Allan that you are the true Supreme Overdeity of Informatics at WCI, you've decided to attempt the question.

#### Constraints

For all subtasks:

##### Subtask 1 [20%]

##### Subtask 2 [25%]

##### Subtask 3 [55%]

No additional constraints.

#### Input Specification

The first line contains the integers .

The next lines contain the queries with query per line.

#### Output Specification

Output the answer to each query on its own line.

#### Sample Input

```
6 17 17
5 100
5 11
10 7
8 9
17 1
1 17
```

#### Sample Output

```
2
-1
-1
1
0
4
```

#### Sample Explanation

Here are the bitmask representations of the queries (the bits in brackets represent the added bits):

`101 -> 1[00]01`

:- so this query is impossible.
- is
`1010`

in binary and is`10001`

in binary. It can be shown that this query is impossible to complete. `1000 -> 1000[1]`

:`10001 -> 10001`

:`1 -> [1000]1`

:

## Comments