Submit
 

F : Eggs

Time Limit : 5 sec, Memory Limit : 262142 KB

F : 卵 / Eggs

TL : 5 sec, ML : 256 MB, Diff Judge

問題文

1 か月前のことである. 小学生の肉西君は夏休みの宿題をやっていなかった. そこで自由研究は家にあった卵の強度を調べることにした.

この研究において,卵を高さ H から落としても割れず, 高さ H+1 から落とすと割れるとき, その卵の強度は H であると定義する. ここで H は非負整数であり,非負整数以外の高さから落とすことは無いとする. 肉西くんは卵を 1 つ落下させる実験を行う. 実験の結果は割れるか割れないかのいずれかである. また,卵の強度は全て同じである.つまり,どの卵を用いても実験の結果は同じである.

肉西くんは高さ 1 から N までの整数の高さの段からなる階段と, 強度が不明な E 個の卵を用意した. 高さ 0 では割れず,高さ N+1 では割れるということは既にわかっている. 肉西くんは各段と同じ高さから地面に向かって落とし,その度に卵が割れたか割れなかったかを調べる. このとき割れた卵は二度と使えないが,割れなかった場合は再利用できる. この実験を卵が残っている限り続けることができる. 何度か実験を繰り返し,上に定めた H が求まったとき,卵の強度が求まったとする.

夏休み終了まで後数日しか無い. 最小の回数で実験を終わらせないと間に合わない. そこで,肉西くんの兄であるあなたは,卵の強度を知るために 落とす回数が少なくなるように最適な方法をとった場合に 必要な実験回数の最大値を求めるプログラムを書くことにした.

入力

T
N_1 E_1N_T E_T

1 つのファイルに複数のテストケースが含まれる. 1 行目に整数 T が与えられる. 1+i 行目に i 番目のテストケース E_i, N_i が与えられる

制約

  • 整数である
  • 1 ≤ T ≤ 1000
  • 1 ≤ N_i ≤ 10^{18}
  • 1 ≤ E_i ≤ 50
  • 出力が 50 を超えるような入力は含まれない

出力

i 番目のテストケースに対する答えを i 行目に出力せよ. 全体で T 行にわたる.

サンプル

サンプル入力1

3
5 1
5 2
1 2

サンプル出力1

5
3
1
  • 1 つ目の場合
    • 卵が 1 つしかないため 1 段目から順に落としていくしかない
  • 2 つ目の場合
    • まず 2 段目から落とす
    • 2 段目から落として割れた場合 1 段目から落とす
    • 2 段目から落として割れなかった場合 4 段目から落とす
    • 1 段目から落として割れた場合実験終了
    • 1 段目から落として割れなかった場合実験終了
    • 4 段目から落として割れた場合 3 段目から落とす
    • 4 段目から落として割れなかった場合 5 段目から落とす
    • 3 段目から落として割れた場合実験終了
    • 3 段目から落として割れなかった場合実験終了
    • 5 段目から落として割れた場合実験終了
    • 5 段目から落として割れなかった場合実験終了
  • 3 つ目の場合
    • 1 段目から落として実験終了