有一次,n个人同时签到了刚刚开业、但已经彻底官僚化的组织(简称TBO)的接待处。由于该组织完全官僚化,因此每天只能接待和照顾一个人。结果,n 个人中的每一个人都在接下来的 n 天中的某一天进行了预约,并且没有两个人在同一天进行了预约。
然而,组织工作人员对自己的工作非常不负责任,因此没有一个签名者被告知预约的具体日期。了解人们何时应该来的唯一方法是向 TBO 写一些请求。
请求表由 m 个空行组成。在每一行中都可以写入签名者的姓名(也可以留空)。禁止以相同的形式写一个人的名字两次,此类请求将被忽略。 TBO 对书面请求的响应速度非常快,但回复格式的质量非常差 - 也就是说,响应包含请求表中所有人的正确预约日期,但日期的顺序完全是随机的。响应当天结束时同时到达的所有请求(每个响应指定它响应的请求)。
幸运的是,你不在这n个幸运儿之中。作为观察员,您有以下任务 - 给定 n 和 m,确定提交给 TBO 的最少请求数量,以明确确定每个人的预约日期。
输入
第一行包含一个整数 t (1 ≤ t ≤ 1000) — 测试用例的数量。接下来的每行 t 行包含两个整数 n 和 m (1 ≤ n, m ≤ 109) — 相应地,在 TBO 预约的人数和请求表中的空行数。
输出
打印 t 行,每行包含相应测试用例的答案(按照输入中给出的顺序)——提交给 TBO 的最小请求数。
示例
输入 #1
5 4 1 4 2 7 3 1 1 42 7
输出 #1
3 2 3 0 11
注意
在第一个示例中,您需要使用三个不同的名称向 TBO 提交三个请求。当您知道四分之三的人的约会日期时,您可以通过排除法找到第四个人的日期,因此您不需要第四个请求。
在第二个示例中,您只需要两个请求。让我们对人员从 1 到 4 进行编号,并在第一个请求中提及人员 1 和 2,在第二个请求中提及人员 1 和 3。不难看出,无论从TBO获得什么答案,我们都可以清楚地确定每个人的预约日期。
在第四个样本中,只有一个人报名了预约。他不需要提交任何请求——他的预约日期是明天。