Easy Scheduling

Description:

Input:

The first line of the input contains the number of tests $$$t$$$ ($$$1 \leq t \leq 5\cdot 10^5$$$). Each of the next $$$t$$$ lines contains the description of a test. A test is described by two integers $$$h$$$ ($$$1 \leq h \leq 50$$$) and $$$p$$$ ($$$1 \leq p \leq 10^4$$$) — the height of the full binary tree and the number of processes. It is guaranteed that all the tests are different.

Output:

For each test output one integer on a separate line — the smallest number of time moments the system needs to perform all the tasks.

Sample Input:

3
3 1
3 2
10 6

Sample Output:

7
4
173

Note:

Let us consider the second test from the sample input. There is a full binary tree of height $$$3$$$ and there are two processes. At the first moment of time, there is only one ready task, $$$1$$$, and $$$p_1$$$ performs it. At the second moment of time, there are two ready tasks, $$$2$$$ and $$$3$$$, and the processes perform them. At the third moment of time, there are four ready tasks, $$$4$$$, $$$5$$$, $$$6$$$, and $$$7$$$, and $$$p_1$$$ performs $$$6$$$ and $$$p_2$$$ performs $$$5$$$. At the fourth moment of time, there are two ready tasks, $$$4$$$ and $$$7$$$, and the processes perform them. Thus, the system spends $$$4$$$ moments of time to perform all the tasks.