多集是指集合中可以允许有重复元素的整数集合，整数的顺序无关紧要。例如，{2,2,4}，{2,4,2}都是多集。

现给我们一个多集S。最开始时，这个多集只包含一个正整数n，即S={n}。另外，再给我们一个正整数k。

在一次操作中，您可以选择多集中任意一个正整数u，然后向S中插入不超过k个正整数，使所有插入的正整数之和等于u。

求使多集S中包含n个1的最小操作数。

第一行一个整数t(1 ≤t≤ 1000)：测试样例数。

接下来共t行，每个测试样例一行两个整数n和k(1≤n≤1000, 2≤k≤1000)：n为多集中的起始元素，k为每次插入多集中的最大元素个数。

    输出共t行，每个测试用例一行一个整数，为使得多集中包含n个1所需要的最少操作次数；