Responsive image

问题 H: 神奇天平

问题 H: 神奇天平

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 57
[提交][状态][讨论版][命题人:]

题目描述

出题人作为苦逼的研究生被导师布置了一项任务，他的面前摆有n件物品，这n件物品中仅有一件物品比其他物品重。而出题人则拥有一个神奇天平，该天平最多可以放置m样东西，每次称量可以得出哪样东西最重，或者放置的若干样东西一样重。
现在出题人想知道，他至少称多少次一定能找出这件较重的物品？

输入描述

第一行一个正整数T，表示数据组数T≤1e5。
对于每组数据，输入两个整数n,m，2≤n≤1e9,2≤m≤1e9。

输出描述

对于每组数据，输出保证一定能找到较重物品的最少称量次数。

样例输入

2
9 2
8 2

样例输出

2
2

提示


对于样例1：



首先把9件物品分成三堆，每堆3件，然后将其中两堆放入神奇天平。若一样重则表示重的物品在没放入的那堆中，否则通过天平我们可以找到重的那堆。



把重的那堆三件物品中的其中两件再次放入神奇天平，若一样重则表示剩下的那件物品就是重的物品，否则通过天平我们可以找到重的那件物品。



样例2的答案可类比以上过程得到。

[提交][状态]
ACM算法攻关部