Berland 州立大学已收到操作系统的新更新。最初它仅安装在 $$$1$$$-st 计算机上。
更新文件应复制到所有 $$$n$$$ 计算机。计算机未连接到互联网,因此将更新文件从一台计算机传输到另一台计算机的唯一方法是使用跳线(直接连接两台计算机的电缆)复制它们。一次只能将一根跳线连接到计算机。因此,从安装了更新文件的任何计算机上,都可以在一小时内将它们复制到其他计算机上。
如果 Berland 州立大学只有 $$$k$$$ 跳线,您的任务是求出将更新文件复制到所有 $$$n$$$ 计算机所需的最少小时数。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。
每个测试用例由一行组成,其中包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 10^{18}$$$) — 计算机的数量和跳线的数量。
输出
对于每个测试用例,打印一个整数 - 将更新文件复制到所有 $$$n$$$ 计算机所需的最少小时数。
示例
输入 #1
4 8 3 6 6 7 1 1 1
输出 #1
4 3 6 0
注意
让我们考虑一下示例的测试用例:
- $$$n=8$$$, $$$k=3$$$:在第一个小时内,我们将更新文件从计算机$$$1$$$复制到计算机$$$2$$$; 在第二个小时内,我们将更新文件从计算机$$$1$$$复制到计算机$$$3$$$,并从计算机$$$2$$$复制到计算机$$$4$$$; 在第三个小时内,我们将更新文件从计算机$$$1$$$复制到计算机$$$5$$$,从计算机$$$2$$$复制到计算机$$$6$$$,从计算机$$$3$$$复制到计算机$$$7$$$; 在第四个小时内,我们将更新文件从计算机$$$2$$$复制到计算机$$$8$$$。
- $$$n=6$$$, $$$k=6$$$:在第一个小时内,我们将更新文件从计算机$$$1$$$复制到计算机$$$2$$$; 在第二个小时内,我们将更新文件从计算机$$$1$$$复制到计算机$$$3$$$,并从计算机$$$2$$$复制到计算机$$$4$$$; 在第三个小时内,我们将更新文件从计算机$$$1$$$复制到计算机$$$5$$$,并从计算机$$$2$$$复制到计算机$$$6$$$。
- $$$n=7$$$, $$$k=1$$$:在第一个小时内,我们将更新文件从计算机$$$1$$$复制到计算机$$$2$$$; 在第二个小时内,我们将更新文件从计算机$$$1$$$复制到计算机$$$3$$$; 第三个小时,我们将更新文件从计算机$$$1$$$复制到计算机$$$4$$$; 在第四个小时内,我们将更新文件从计算机$$$4$$$复制到计算机$$$5$$$; 在第五个小时内,我们将更新文件从计算机$$$4$$$复制到计算机$$$6$$$; 在第六个小时内,我们将更新文件从计算机$$$3$$$复制到计算机$$$7$$$。