Guessing Game

Hektor loves looking after his younger sister Kornelia, and the two never run out of games to play. Today they are playing a guessing game.

The game needs $N$ square cells laid out in a row. First, Kornelia paints a run of cells starting from the front: she paints the first $x$ cells, where $x$ can be any value from $0$ to $N$ (she may paint none of them, or all of them). When she is done, she covers each cell with a piece of paper so you cannot tell whether it was painted.

Now it is Hektor's turn. He must figure out how many cells Kornelia painted. Hektor may uncover cells of his choice over several rounds; in each round he may uncover (simultaneously) at most $K$ of the still-covered cells. Each uncovered cell reveals whether or not it was painted.

Compute the minimum number of rounds for which a strategy of choosing which cells to uncover exists that guarantees determining the number of painted cells.

The first line contains the number of test cases $Z$ ($1 \le Z \le 10$). Each of the next $Z$ lines contains the two natural numbers $N$ and $K$ described above, separated by a space ($1 \le N, K \le 10^6$).

For each test case, print on its own line the minimum number of rounds that guarantees success.

For $N = 5$, $K = 2$, two rounds are enough, for example with the following strategy. In the first round Hektor uncovers cells 2 and 4.

• If both cells 2 and 4 turn out painted, uncovering cell 5 in the second round tells whether Kornelia painted 4 or 5 cells.
• If cell 2 is painted but cell 4 is not, uncovering cell 3 in the second round tells whether she painted 2 or 3 cells.
• If neither cell 2 nor cell 4 is painted, uncovering cell 1 in the second round tells whether she painted 1 cell or none.

One round, on the other hand, is not enough: whatever cells Hektor uncovers in the first round, it can still happen that he cannot pin down the count. For example, if he uncovers cells 2 and 4 and only cell 2 is painted, he cannot tell 2 from 3; and if he uncovers cells 1 and 2 and both are painted, he cannot tell which of 2, 3, 4, or 5 cells were painted.