整数 $n$ が与えられます。この整数に対して、以下の2種類の操作を行うことができます。

• $n \leftarrow n+2$：$n$ を $2$ 増やす。
• $\sqrt n$ が整数である場合、$n \leftarrow \sqrt n$：$n$ の平方根をとる。この操作を行うと $1$ 点を獲得する。

$k$ 点を獲得するために必要な操作回数の最小値を求めてください。

入力

本問は複数のテストケースを含みます。

入力の最初の行には、テストケースの番号 $c$ とテストケースの数 $t$ が含まれます。$c=0$ はそのテストケースがサンプルであることを示します。

続いて各テストケースが順に入力されます。各テストケースは以下の通りです。

• $1$ 行に $2$ つの正整数 $n, k$ が含まれます。

出力

各テストケースについて：

• $k$ 点を獲得するために必要な操作回数の最小値を $1$ 行で出力してください。

入出力例

入力 1

0 5
6 1
1 3
14514 23333
2011112920110906 1
3 1919810233114514

出力 1

6
3
46860
15268726
7679240932458056

注記

このサンプルには $5$ つのテストケースが含まれています。

• $1$ 番目のテストケースでは、操作 $1$ を $5$ 回行い、その後に操作 $2$ を $1$ 回行うことで達成できます。これが最小の $6$ 回であることが証明できます。
• $2$ 番目のテストケースでは、操作 $2$ を $3$ 回行うことで達成できます。これが最小の $3$ 回であることが証明できます。

制約

すべてのテストケースにおいて、以下が成り立ちます。

• $1 \le t \le 10^5$
• $1 \le n, k \le 10^{18}$

• 特殊な性質：$t=3$ であることが保証されます。