問題文

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

• $NK$

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

入力

$Q$
$N_0{K}_0$
$\cdots$
$N_{Q-1}{K}_{Q-1}$

• $1\le Q\le 10$
• $1\le N_i,K_i\le {10}^9$
• 入力はすべて整数

出力

$Q$ 行出力し，$i$ 行目には $i$ 番目の $\mathrm{q}\mathrm{u}\mathrm{e}\mathrm{r}\mathrm{y}$ の答えを整数で一行に出力してください．

サンプル

サンプル1

入力サンプルをコピー

入力

3
4 2
41 3
100 1

出力

2
4
99

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