C. Max Person
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You have an infinite-storey building. Each floor has exactly $$$n$$$ rooms, and each room can accommodate one person.

Placing one person on floor $$$x$$$ (where floors are $$$1$$$-indexed: $$$x=1,2,3,\dots$$$) costs $$$2^{x}$$$ units of budget. You are given a total budget of $$$m$$$ and you must spend all of it.

Your task is to determine the maximum possible number of people you can accommodate while spending exactly $$$m$$$. If it is impossible to spend the budget exactly, output $$$-1$$$.

Input

The first line contains an integer $$$T$$$ $$$(1 \le T \le 10^5)$$$ — the number of test cases.

Each of the next $$$T$$$ lines contains two integers $$$n$$$ $$$(1 \le n \le 10^{18})$$$ and $$$m$$$ $$$(1 \le m \le 10^{18})$$$.

Output

For each test case, print a single integer on its own line — the maximum number of people that can be accommodated while spending exactly $$$m$$$, or $$$-1$$$ if it is impossible.

Example
Input
2
5 10
1 30
Output
5
4
Note

For the first case: $$$n = 5$$$, $$$m = 10$$$. It is optimal to place 5 people on floor 1. Cost is $$$5\cdot2^1 = 10$$$ — exact, so the answer is $$$5$$$.

For the second case 2: $$$n = 1, m = 30$$$. At most one person can be accommodated per floor. If we place one person on floors $$$1, 2, 3, 4$$$ (cost $$$2 + 4 + 8 + 16 = 30$$$). Total people = $$$4$$$, which is maximal since each floor can host only one person.