← 返回题目列表

Codeforces · 1578/E

E. 轻松安排

中文机器翻译题面 查看原题

Eonathan Eostar 决定学习多处理器系统的魔力。他有一个高度为 $$$h$$$ 的完整二叉任务树。一开始,树中只有一个准备好的任务 - 根中的任务。在每个时刻,$$$p$$$ 进程最多选择 $$$p$$$ 就绪任务并执行它们。之后,父母执行的任务就为下一个时刻做好了准备。一旦任务准备好,它就会保持准备状态直到执行。

您应计算系统执行所有任务所需的最小时刻数。

输入

输入的第一行包含测试数量 $$$t$$$ ($$$1 \leq t \leq 5\cdot 10^5$$$)。接下来的每一行 $$$t$$$ 都包含测试的描述。测试由两个整数 $$$h$$$ ($$$1 \leq h \leq 50$$$) 和 $$$p$$$ ($$$1 \leq p \leq 10^4$$$) 描述 - 完整二叉树的高度和进程数。保证所有测试都是不同的。

输出

对于每个测试,在单独的行上输出一个整数 - 系统执行所有任务所需的最小时刻数。

示例

输入 #1

3
3 1
3 2
10 6

输出 #1

7
4
173

注意

让我们考虑样本输入的第二个测试。有一个高度为 $$$3$$$ 的满二叉树,有两个进程。在第一时刻,只有一个就绪任务 $$$1$$$,$$$p_1$$$ 执行它。在第二个时刻,有两个就绪任务,$$$2$$$ 和 $$$3$$$,并且进程执行它们。在第三时刻,有四个就绪任务:$$$4$$$、$$$5$$$、$$$6$$$和$$$7$$$,$$$p_1$$$执行$$$6$$$,$$$p_2$$$执行$$$5$$$。在第四个时刻,有两个就绪任务,$$$4$$$ 和 $$$7$$$,并且进程执行它们。因此,系统花费 $$$4$$$ 时间来执行所有任务。