問題文

niuez くんは木を美しく作る技術を持っており，美しい木を求める客から依頼を受けています．
niuez くんの住む街ではコンパクトな木（compactree）が流行っており，それを作成する query を niuez くんは大量に預かっています．
次の $Q$ 個の query を処理してください．

• $N \ K$

  • $N$ 個の頂点と$N-1$個の辺からなる $K$ 分有向木（すべての頂点の子が高々 $K$ 個であるような木）のうち，深さの最小値を求める．
  • ここで，深さとは根から各頂点へのパスに含まれる辺の数のうち，最大のものを指します．

入力

$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$
• 入力はすべて整数

出力

$Q$ 行出力し，$i$ 行目には $i$ 番目の ${\rm query}$ の答えを整数で一行に出力してください．

サンプル

サンプル1

入力

3
4 2
41 3
100 1

出力

2
4
99

最初のクエリは例えば以下のように木をつくると高さを2にできます.
子の数は頂点$2$の2個が最大で, 入力の条件を満たしています.