CF1578E.Easy Scheduling

Eonathan Eostar decided to learn the magic of multiprocessor systems. He has a full binary tree of tasks with height $h$. In the beginning, there is only one ready task in the tree — the task in the root. At each moment of time, $p$ processes choose at most $p$ ready tasks and perform them. After that, tasks whose parents were performed become ready for the next moment of time. Once the task becomes ready, it stays ready until it is performed.

You shall calculate the smallest number of time moments the system needs to perform all the tasks.

伊奥纳坦·伊奥斯塔尔决定学习多处理器系统的魔法。他有一棵高度为 $h$ 的满二叉树形式的任务树。初始时，树中只有一个就绪任务——即根节点处的任务。在每一时刻，$p$ 个处理器最多选择 $p$ 个就绪任务并执行它们。执行完毕后，那些父任务已被执行的任务将在下一时刻变为就绪状态。一个任务一旦变为就绪状态，便会一直保持就绪状态，直至被执行。

你需要计算系统执行完所有任务所需的最少时间时刻数。

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.

输入的第一行包含测试用例的数量 $t$（$1 \leq t \leq 5\cdot 10^5$）。接下来的 $t$ 行每行描述一个测试用例。每个测试用例由两个整数 $h$（$1 \leq h \leq 50$）和 $p$（$1 \leq p \leq 10^4$）描述，分别表示满二叉树的高度和进程数量。保证所有测试用例互不相同。

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

对于每组测试数据，输出一行一个整数——系统完成所有任务所需的最少时间点数量。

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.

我们考虑样例输入中的第二个测试用例。该测试用例对应一棵高度为 $3$ 的满二叉树，且有两个进程。在第一个时间点，仅有一个就绪任务 $1$，由进程 $p_1$ 执行。在第二个时间点，有两个就绪任务 $2$ 和 $3$，两个进程分别执行它们。在第三个时间点，有四个就绪任务 $4$、$5$、$6$ 和 $7$，其中 $p_1$ 执行任务 $6$，$p_2$ 执行任务 $5$。在第四个时间点，有两个就绪任务 $4$ 和 $7$，两个进程分别执行它们。因此，系统共花费 $4$ 个时间点来完成所有任务。