409408: GYM103503 B Binary Search Search

B. Binary Search Searchtime limit per test1 secondmemory limit per test64 megabytesinputstandard inputoutputstandard output

Binary Search Search (BSS) is a cross between Breadth First Search and Binary Search. Its pseoudocode can be found below:

read n
queue of pairs q
push(q,pair(1,n))

while(q is not empty){

    pair current = front(q)

    mid = (current.first + current.second) / 2
    print mid

    if(mid > current.first)
         push(q,pair(current.first, mid - 1))

    if(mid < current.second)
         push(q,pair(mid + 1, current.second))

    pop_front(q)
}

For example, if $$$n=7$$$, this algorithm will print [$$$4$$$ $$$2$$$ $$$6$$$ $$$1$$$ $$$3$$$ $$$5$$$ $$$7$$$].

Even though BSS doesn't have any practical applications, you are curious as to how long it takes for this algorithm to print certain integers. More formally, you are given $$$t$$$ testcases, each testcase containing two integers $$$n$$$ and $$$k$$$. For each testcase, print one integer $$$p$$$ — the position of $$$k$$$ in the array printed by BSS.

Input

The first line of input contains one integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of testcases. Each testcase contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 10^{18}$$$) — as described in the statement.

Output

For each testcase, print one integer $$$p$$$ — the position of $$$k$$$ in the array printed by BSS.

Scoring

• Subtask 1 (20 points): $$$1 \le t,n \le 1000$$$;
• Subtask 2 (30 points): $$$1 \le t \le 1000$$$, $$$1 \le n \le 10^9$$$;
• Subtask 3 (24 points): $$$1 \le t \le 10^4$$$;
• Subtask 4 (26 points): No further constraints

ExampleInput

7
7 1
7 2
7 3
7 4
7 5
4 1
4 4

Output

4 2 5 1 6 2 4 

Note

For $$$n=7$$$, BSS will print [$$$4$$$ $$$2$$$ $$$6$$$ $$$1$$$ $$$3$$$ $$$5$$$ $$$7$$$]. $$$1$$$ is the fourth printed integer, $$$2$$$ is the second, $$$3$$$ is the fifth, $$$4$$$ is the first and $$$5$$$ is the sixth.

For $$$n=4$$$, BSS will print [$$$2$$$ $$$1$$$ $$$3$$$ $$$4$$$]. $$$1$$$ is the second printed integer and $$$4$$$ is the fourth.