Problem Description

Yoshinow2001 is making data for his problem. He wants to generate a random permutation of $\lbrace 0,\dots,n-1\rbrace$ , so he used the following algorithm:

Here, we can assume that the function $rand() \bmod n$ is able to generate integer randomly in the set $\lbrace 0,\dots,n-1\rbrace$ with equal probability.

Now Yoshinow2001 is concerned that this algorithm is not random enough ------ after all, if you want to randomize a permutation, the expected number of elements for $a_i\neq i$ should be $n-1$. So he wants to ask what the mathematical expectation of the final $ans$ is.

Input

The first line of input is a positive integer $T(1\leq T\leq 10^5)$ representing the number of data cases.

For each cases consists of a single line of two integers $n,m$, separated by a space.
Where $1\leq n\leq 10^{18}$,$0\leq m\leq 10^{18}$, ensure that $n$ is not a multiple of $998\ 244\ 353$.

Output

For each cases, output a line with a positive integer representing the answer $\bmod 998\ 244\ 353$.

3
1 0
1 1
2 1

0
0
1