Problem Statement

niuez has the skill of building trees beautifully, and takes requests from customers seeking beautiful trees.
In the town where niuez lives, compact trees (compactree) are in fashion, and niuez has been entrusted with a large number of queries to build them.
Process the following $Q$ queries.

• $N \ K$

  • Among $K$-ary directed trees (trees in which every vertex has at most $K$ children) consisting of $N$ vertices and $N-1$ edges, find the minimum possible depth.
  • Here, the depth refers to the maximum, over all vertices, of the number of edges on the path from the root to that vertex.

Input

$Q$
$N_0\ K_0$
$\cdots$
$N_{Q-1}\ K_{Q-1}$

• $1 \leq Q \leq 10$
• $1 \leq N_i, K_i \leq 10^9$
• All inputs are integers.

Output

Output $Q$ lines. On the $i$-th line, output the answer to the $i$-th ${\rm query}$ as an integer.

Sample

Sample 1

Input

3
4 2
41 3
100 1

Output

2
4
99

For the first query, the height can be made 2 by building the tree as shown below, for example.
The maximum number of children is 2, at vertex $2$, which satisfies the condition of the input.