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$$$ 时间来执行所有任务。