题目描述
小天得到了传说中(又是传说中的.....)神圣之蛋,一大堆.....他可真够幸运的......
小天一共得到M个神圣之蛋,小天想知道这些神圣之蛋的坚硬度L。他是通过不断从一幢N层的楼上向下扔神圣之蛋来确定L的(这样浪费粮食,五雷轰顶之)。当神圣之蛋从第L层楼及以下楼层落下时是不会碎的,但从第(L+1)层楼及以上楼层向下落时会摔碎。如果神圣之蛋未摔碎,还可以继续使用;但如果神圣之蛋全碎了却扔未确定L。显然小天失败了,小天当然希望他能成功。
所有的神圣之蛋都有相同的坚硬度,小天想知道在最坏情况下确定E所要的最少次数。
20%的数据N<=100000,M<=100,T<=5
50%的数据N<=100000000,M<=100000,T<=50。
100%的数据N<=1000000000,M<=100000,T<=100。
神圣之蛋的坚硬度L<=n。
样例说明:因为只有1个神圣之蛋,小天不想失败,所以只好从1层到N层依次扔下,一旦在第(L+1)层摔碎,那么L便确定了。
不是所有的神圣之蛋都必须用完。
输入格式
共T组数据,T<=10
第一行,一个数T
接下来T行,每行2个数字n,m(意义如上所示)
输出格式
T行数,每行一个数字即在最坏的情况下最少次数。
样例输入
样例输出