問題文

N 人のボランティアが KeioPC のお手伝いをしてくれます。そこで、色付きのリストバンドを付けてもらい N 人全員を区別することにしました。

全ての人はちょうど M 個のリストバンドを腕につける必要があります。ただし、どの相異なる 2 人のボランティアも、リストバンドの色の多重集合が一致してはいけません。

必要なリストバンドの色数の最小値を求めてください。

T 個のテストケースが与えられるので、それぞれについて解いてください。

制約

• 1 \le T \le 10
• 1 \le N \le 10^{18}
• 1 \le M \le 10^{18}
• 入力はすべて整数

入力例 1

7
3 2
12 10
35 4
1000000000000000000 1
18350110 2
19010203 3
20260215 4

出力例 1

2
3
4
1000000000000000000
6058
484
147

1 番目のテストケースについて、例えば赤と青の 2 色のリストバンドを用意して、以下のように付けてもらうと条件を満たします。

• 1 人目には、赤のリストバンドを 2 個付けてもらう。
• 2 人目には、青のリストバンドを 2 個付けてもらう。
• 3 人目には、赤と青のリストバンドを 1 個ずつ付けてもらう。

1 色以下では条件を満たせないため、答えは 2 です。