You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 512.0 MB

# Problem
A multiset is a set of numbers in which there can be equal elements, and the order of the numbers does not matter. For example, $$$\{2,2,4\}$$$ is a multiset.

You have a multiset $$$S$$$. Initially, the multiset contains only one positive integer $$$n$$$. That is, $$$S=\{n\}$$$. Additionally, there is a given positive integer $$$k$$$.

In one operation, you can select any positive integer $$$u$$$ in $$$S$$$ and remove one copy of $$$u$$$ from $$$S$$$. Then, insert no more than $$$k$$$ positive integers into $$$S$$$ so that the sum of all inserted integers is equal to $$$u$$$.

Find the minimum number of operations to make $$$S$$$ contain $$$n$$$ ones.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). Description of the test cases follows.

The only line of each testcase contains two integers $$$n,k$$$ ($$$1\le n\le 1000,2\le k\le 1000$$$).

## Output Format
For each testcase, print one integer, which is the required answer.

## Examples
```input
4
1 5
5 2
6 3
16 4
```
```output
0
4
3
5
```

## Note
For the first test case, initially $$$S=\{1\}$$$, already satisfying the requirement. Therefore, we need zero operations.

For the second test case, initially $$$S=\{5\}$$$. We can apply the following operations:

- Select $$$u=5$$$, remove $$$u$$$ from $$$S$$$, and insert $$$2,3$$$ into $$$S$$$. Now, $$$S=\{2,3\}$$$.
- Select $$$u=2$$$, remove $$$u$$$ from $$$S$$$, and insert $$$1,1$$$ into $$$S$$$. Now, $$$S=\{1,1,3\}$$$.
- Select $$$u=3$$$, remove $$$u$$$ from $$$S$$$, and insert $$$1,2$$$ into $$$S$$$. Now, $$$S=\{1,1,1,2\}$$$.
- Select $$$u=2$$$, remove $$$u$$$ from $$$S$$$, and insert $$$1,1$$$ into $$$S$$$. Now, $$$S=\{1,1,1,1,1\}$$$.

Using $$$4$$$ operations in total, we achieve the goal.

For the third test case, initially $$$S=\{6\}$$$. We can apply the following operations:

- Select $$$u=6$$$, remove $$$u$$$ from $$$S$$$, and insert $$$1,2,3$$$ into $$$S$$$. Now, $$$S=\{1,2,3\}$$$.
- Select $$$u=2$$$, remove $$$u$$$ from $$$S$$$, and insert $$$1,1$$$ into $$$S$$$. Now, $$$S=\{1,1,1,3\}$$$.
- Select $$$u=3$$$, remove $$$u$$$ from $$$S$$$, and insert $$$1,1,1$$$ into $$$S$$$. Now, $$$S=\{1,1,1,1,1,1\}$$$.

Using $$$3$$$ operations in total, we achieve the goal.

For the fourth test case, initially $$$S=\{16\}$$$. We can apply the following operations:

- Select $$$u=16$$$, remove $$$u$$$ from $$$S$$$, and insert $$$4,4,4,4$$$ into $$$S$$$. Now, $$$S=\{4,4,4,4\}$$$.
- Repeat for $$$4$$$ times: select $$$u=4$$$, remove $$$u$$$ from $$$S$$$, and insert $$$1,1,1,1$$$ into $$$S$$$.

Using $$$5$$$ operations in total, we achieve the goal.

Now solve the problem and return the code.