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 python3.

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:
```python
<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.