多重集是一组数字,其中可以有相同的元素,并且数字的顺序并不重要。例如,$$$\{2,2,4\}$$$ 是多重集。
您有一个多重集$$$S$$$。最初,多重集仅包含一个正整数$$$n$$$。即$$$S=\{n\}$$$。此外,还有一个给定的正整数$$$k$$$。
在一次操作中,您可以选择 $$$S$$$ 中的任意正整数 $$$u$$$ 并从 $$$S$$$ 中删除 $$$u$$$ 的一份副本。然后,向$$$S$$$中插入不超过$$$k$$$个正整数,使得所有插入的整数之和等于$$$u$$$。
求使 $$$S$$$ 包含 $$$n$$$ 的最少操作数。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。
每个测试用例的唯一行包含两个整数 $$$n,k$$$ ($$$1\le n\le 1000,2\le k\le 1000$$$)。
输出
对于每个测试用例,打印一个整数,这是所需的答案。
示例
输入 #1
4 1 5 5 2 6 3 16 4
输出 #1
0 4 3 5
注意
对于第一个测试用例,最初$$$S=\{1\}$$$,已经满足要求。因此,我们需要零操作。
对于第二个测试用例,最初为 $$$S=\{5\}$$$。我们可以应用以下操作:
- 选择$$$u=5$$$,从$$$S$$$中删除$$$u$$$,并将$$$2,3$$$插入$$$S$$$中。现在,$$$S=\{2,3\}$$$。
- 选择$$$u=2$$$,从$$$S$$$中删除$$$u$$$,并将$$$1,1$$$插入$$$S$$$。现在,$$$S=\{1,1,3\}$$$。
- 选择$$$u=3$$$,从$$$S$$$中删除$$$u$$$,并将$$$1,2$$$插入$$$S$$$中。现在,$$$S=\{1,1,1,2\}$$$。
- 选择$$$u=2$$$,从$$$S$$$中删除$$$u$$$,并将$$$1,1$$$插入$$$S$$$。现在,$$$S=\{1,1,1,1,1\}$$$。
总共使用 $$$4$$$ 操作,我们实现了目标。
对于第三个测试用例,最初为 $$$S=\{6\}$$$。我们可以应用以下操作:
- 选择$$$u=6$$$,从$$$S$$$中删除$$$u$$$,并将$$$1,2,3$$$插入$$$S$$$。现在,$$$S=\{1,2,3\}$$$。
- 选择$$$u=2$$$,从$$$S$$$中删除$$$u$$$,并将$$$1,1$$$插入$$$S$$$。现在,$$$S=\{1,1,1,3\}$$$。
- 选择$$$u=3$$$,从$$$S$$$中删除$$$u$$$,并将$$$1,1,1$$$插入$$$S$$$。现在,$$$S=\{1,1,1,1,1,1\}$$$。
总共使用 $$$3$$$ 操作,我们实现了目标。
对于第四个测试用例,最初为 $$$S=\{16\}$$$。我们可以应用以下操作:
- 选择$$$u=16$$$,从$$$S$$$中删除$$$u$$$,并将$$$4,4,4,4$$$插入$$$S$$$。现在,$$$S=\{4,4,4,4\}$$$。
- 重复$$$4$$$次:选择$$$u=4$$$,从$$$S$$$中删除$$$u$$$,并将$$$1,1,1,1$$$插入$$$S$$$。
总共使用 $$$5$$$ 操作,我们实现了目标。