N and K

Time Limit : 4 sec, Memory Limit : 131072 KB

H - N and K

1以上N以下の整数からなる狭義単調増加数列で,数列の要素からどの2つの異なる数を取ってきても 他方が一方を割り切ることがないようなものを考える. そのような数列のうち,とりうる最大の長さをLとして,そのような数列(a_1,a_2,...,a_L)を考える. この数列のK番目の要素a_Kを求めよ.ただし,そのような数列(a_1...a_L)が複数個存在する場合は, a_Kの値としてとりうる最小の値を出力せよ. また,K > Lのときは-1を出力せよ.

入力形式

入力は複数の入力からなる.入力の数はCセットあり,i番目の入力はN_i, K_iである. テストケースは以下の形式で与えられる.

C
N_1 K_1N_C K_C

出力形式

出力はC行からなる. i行目の出力は,N_iK_iについての答えである.

制約

  • 1 \leq C \leq 10^5
  • 1 \leq N_i \leq 10^{18}
  • 1 \leq K_i \leq N_i
  • 入力値はすべて整数である.

この問題の判定には,50 点分のテストケースのグループが設定されている.このグループに含まれるテストケースは上記の制約に加えて下記の制約も満たす.

  • C=1, N_i \leq 50

入出力例

入力例1

5
3 2
5 2
8 3
10 1
18 12

出力例1

3
3
5
4
-1

N=3のとき,2番目に小さい要素が最小となる組み合わせの一例として(2,3)が挙げられる.
N=5のとき,2番目に小さい要素が最小となる組み合わせの一例として(2,3,5)が挙げられる.
N=8のとき,3番目に小さい要素が最小となる組み合わせの一例として(3,4,5,7)が挙げられる.
N=10のとき,1番目に小さい要素が最小となる組み合わせの一例として(4,6,7,9,10)が挙げられる.


Source: Kyoto University Programming Contest 2013 , Kyoto, Japan, 2013-07-06
http://www.kupc.jp/
http://kupc2013.contest.atcoder.jp/