Coin Denomination Design - hard

問題文

この問題には Easy 版が存在します。
Easy 版と異なる部分を $\color{red} {\small \texttt{赤色}}$ で示します。

硬貨入れの設計をしていた A 君は、紆余曲折あり A 君が住む国の王様になりました。

A 君の一番の興味は硬貨入れの大きさをできる限り小さくすることなので、そのためにこの国の硬貨の金額を変更することにしました。

硬貨の種類数が $N$ 種類で、紙幣の金額が $B$ であるとき、硬貨の金額 $A_1, A_2, \dots , A_N$ を適切に決めたときの「Coin Purse Design のシミュレーションで必ず硬貨入れの容量が十分であるとされるような硬貨入れの容量（硬貨入れに入る硬貨の枚数）の最小値」の最小値を求めてください。

しかし、国民の使いやすさのため、硬貨の金額 $A_1, A_2, \dots , A_N$ は以下の条件を全て満たす必要があります。

• 硬貨の金額は全て整数
• $1 = A_1 \lt A_2 \lt \dots \lt A_N \lt B$
• 全ての $i = 1, 2, \dots , N-1$ について、$A_{i+1}$ は $A_i$ の倍数
• $\color{red} {\small \texttt{（}} B \ {\small \texttt{は}} \ A_N \ {\small \texttt{の倍数でなくともよい）}}$

$T$ 個のテストケースについて上記問題を解いてください。

制約

• $1 \le T \le 10{,}000$
• $\color{red} 1 \le N \le 50$
• $\color{red} 2 \le B \le 10^{16}$
• 入力は全て整数
• 全ての条件を満たすような硬貨の金額の割り当てが存在するような入力のみが与えられることが保証される

入力

入力は以下の形式で与えられます。 ここで、 $\mathrm{test}_i$ は $i$ 番目のテストケースを表します。

各テストケースは以下の形式で与えられます。

出力

$T$ 行出力せよ。 $i$ 行目には、 $i$ 番目のテストケースに対する答えを出力せよ。

入出力例

入力例

9
1 3
2 9
2 14
3 1000
4 24
3 999
3 1001
10 513
18 10000000000000000

出力例

2
4
5
27
5
26
27
9
121