题目描述

现在你在玩一个益智小游戏。游戏中总共有$n$颗蛋。每颗蛋有一个标号（从1到n，且互不相同）。

你可以每次询问不超过$m$颗蛋的编号。请注意：并不会对应地告诉你这些蛋分别是多少编号，只会告诉你你所选择的蛋的编号集合。例如你选择了第一和第二颗蛋，告诉你编号是3和4，但并不告诉你第一颗蛋是3还是4。

现在你的任务是，最小化询问的总次数，使得你有策略在相应的次数下准确地得到每颗蛋的编号。

下面是一个例子：

共计4颗蛋编号1到4，每次可以询问不超过3颗蛋的编号。

第一次询问第一颗和第二颗；

第二次询问第二颗和第三颗；

共两次询问一定可以得到每颗蛋的编号分别是几。

请注意本题多组数据。

输入格式

第一行一个正整数$t$，表示数据组数。

接下来$t$行，每行两个正整数$n$和$m$，依次表示共$n$颗蛋，每次可以询问至多$m$颗蛋的编号集合。

输出格式

$t$行，每行一个数字表示对应数据下需要多少次询问。

5
4 1
4 2
7 3
1 1
42 7

3
2
3
0
11

数据规模与约定

每组数据点10分，共10组数据。 对所有数据，有$1 \le t \le 1000$

大样例

大样例下载