题目描述

J 村有 $n$ 栋能够上网的房屋。其中一栋房屋里住着一个坏人，他一直使用匿名账号在社交媒体上发表愤怒评论。我们不知道他住在哪一栋房屋中，但希望把他找出来。

变电站里有 $n$ 个开关，每栋房屋对应一个开关。开关打开时，该房屋有电灯，也能够上网；开关关闭时，该房屋没有电灯，因此也无法上网。最初所有开关均处于打开状态。

每个整点，我们可以任意改变开关状态：可以打开一些开关，也可以关闭一些开关。随后的一小时内，我们观察社交媒体：

• 如果坏人所在的房屋有电，他一定会发表评论；
• 如果该房屋没有电，则一定不会出现评论。

调查结束后，我们必须恢复初始状态，即让所有房屋重新有电。

不幸的是，如果坏人所在房屋的电灯被关闭超过 $k$ 次，他就会产生怀疑，我们希望避免这种情况。需要注意，房屋连续停电很长时间并没有问题，限制的是将电灯从亮变为灭的次数。

求为了保证确定坏人住在哪栋房屋，并最终恢复所有房屋供电，最少需要多少小时。

输入格式

第一行包含一个整数 $t$，表示测试数据组数。

接下来 $t$ 行，每行包含两个整数 $n$ 和 $k$：

• $n$ 表示房屋数量；
• $k$ 表示坏人所在房屋的电灯最多允许被关闭的次数。

数据范围

输出格式

对于每组测试数据，输出一个整数，表示确定坏人所在房屋并恢复所有房屋供电所需的最少小时数。

样例

5
3 1
4 1
2 2
17 3
73 6

2
2
1
5
7

样例说明

对于第一组数据，$n=3,k=1$。

第一小时可以关闭第 $1$、$2$ 栋房屋的电灯；一小时后恢复第 $1$ 栋房屋的供电；再过一小时恢复第 $2$ 栋房屋的供电。到第三个小时开始时，我们一定已经知道坏人住在哪栋房屋中，同时所有房屋也已经恢复供电。因此答案为 $2$。