小天得到了传说中(又是传说中的.....)神圣之蛋，一大堆.....他可真够幸运的......

小天一共得到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行数，每行一个数字即在最坏的情况下最少次数。