Problem Statement

Solve the following problem for $T$ test cases.

There is an integer sequence $C$ of length $S$ with all elements initialized to $0$. There is also a variable $X$. Initially, the value of $X$ is equal to $0$.

From here, highlighter performs the following sequence of operations any number of times.

• Choose one positive integer $i$ satisfying $1 \leq i \leq S$, and add $1$ to $C_{i}$.
• Add $\displaystyle\prod_{j \neq i} C_{j}$ to $X$.

Given that $X=N$ when the operations end, find the sum of $\displaystyle\sum_{i=1}^{S} C_{i}$ over all possible post-operation (added at 21:25) $C$. Since the answer can be very large, output it modulo $998244353$.

Constraints

• $1 \leq T \leq 2 \times 10^{5}$
• For each case,
  • all prime factors of $N$ are at most $100$
  • $1 \leq N \leq 10^{18}$
  • $2 \leq S \leq 10^{18}$
• All inputs are integers

Input

The input is given from standard input in the following format. Here, $\mathrm{case}_{i}$ represents the $i$-th case.

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

Each case is given in the following format.

$N~~~S$

Output

Output $T$ lines. On the $i$-th line, output the answer for $\mathrm{case}_{i}$.

Sample

3
3 3
1 2
1 998244353

15
2
0