問題文

※この問題の実行時間制限は6秒です．また，高速な言語の使用を推奨します．

正整数の集合 $S$ が以下を満たすとき，これを良い集合とよびます．

• 正整数 $z$ に対してある $x,y \in S$ が存在して $\dfrac{z}{\gcd(x,y)},\dfrac{\operatorname{lcm}(x,y)}{z}$ が互いに素な整数となるとき，$z \in S$
• $x,y \in S$ のとき $\dfrac{\operatorname{lcm}(x,y)}{\gcd(x,y)}$ は $1$ より大きい $4$ 乗数とならない．

• すべての $\mathscr{S}$ の元の和集合は，$A^B$ の正の約数の集合に等しい．
• 任意の $X,Y \in \mathscr{S}$ について次が成り立つ.
  • $\omega(x,y)$ を $\dfrac{\operatorname{lcm}(x,y)}{\gcd(x,y)}$ の相異なる素因数の個数とする．任意の $x,x^{\prime} \in X$ について，$\min_{y \in Y} \omega(x,y) = \min_{y \in Y} \omega(x^{\prime},y)$

制約

• 入力はすべて整数
• $1 \leq T \leq 10^{6}$
• $1 \leq A \leq 2 \times 10^{7}$
• $1 \leq B \leq 2 \times 10^{6}$

入力

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

$A\ B$

出力

$T$ 行出力してください．$t(1 \leq t \leq T)$ 行目には $t$ 個目のテストケースに対する答えを出力してください．

サンプル

5
12 1
20 2
1 100
9999 9999
16777216 2000000

10
185
1
340129719
720394457