問題文

$T$ 個のテストケースについて以下の問題を解いてください．

すべての要素が $0$ で初期化された長さ $S$ の整数列 $C$ があります．また，変数 $X$ があります．はじめ $X$ の値は $0$ に等しいものとします．

ここからhighlighter君は以下の一連の操作を好きな回数行います．

• $1 \leq i \leq S$ を満たす正整数 $i$ を一つ選び， $C_{i}$ に $1$ を加算する．
• $X$ に $\displaystyle\prod_{j \neq i} C_{j}$ を加算する．

操作終了時に $X=N$ であるとき，ありうる操作後の (21:25追記) すべての $C$ について， $\displaystyle\sum_{i=1}^{S} C_{i}$ の総和を求めてください．ただし答えは非常に大きくなりうるので $998244353$ で割った余りを出力してください．

制約

• $1 \leq T \leq 2 \times 10^{5}$
• 各ケースについて，
  • $N$ の素因数はすべて $100$ 以下
  • $1 \leq N \leq 10^{18}$
  • $2 \leq S \leq 10^{18}$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる．ここで， $\mathrm{case}_{i}$ は $i$ 個目のケースを表す．

$T$
$\mathrm{case}_{1}$
$\mathrm{case}_{2}$
$\vdots$
$\mathrm{case}_{T}$

各ケースは以下の形式で与えられる．

$N~~~S$

出力

$T$ 行出力してください． $i$ 行目には $\mathrm{case}_{i}$ に対する答えを出力してください．

サンプル

3
3 3
1 2
1 998244353

15
2
0