Yoshinow2001 正在为他的题目制作数据。他想要生成一个 $\{0, \dots, n - 1\}$ 的随机排列，因此他使用了以下算法：

输入：$n, m$ 1: $ans = 0$ 2: for $i = 0$ to $n - 1$ do 3: $a[i] = i$ 4: end for 5: for $i = 1$ to $m$ do 6: $\text{swap}(a[\text{rand}() \bmod n], a[\text{rand}() \bmod n])$ 7: end for 8: for $i = 0$ to $n - 1$ do 9: if $a[i] \neq i$ then 10: $ans = ans + 1$ 11: end if 12: end for 输出：$ans$

这里，我们可以假设函数 $\text{rand}() \bmod n$ 能够以相等的概率在集合 $\{0, \dots, n - 1\}$ 中随机生成整数。 现在 Yoshinow2001 担心这个算法不够随机——毕竟，如果你想要随机化一个排列，满足 $a_i \neq i$ 的元素个数的期望值应该是 $n - 1$。 所以他想问最终 $ans$ 的数学期望是多少。

输入格式

第一行输入一个正整数 $T(1 \le T \le 10^5)$，表示数据组数。 对于每组数据，包含一行两个整数 $n, m$，以空格分隔。其中 $1 \le n \le 10^{18}, 0 \le m \le 10^{18}$，保证 $n$ 不是 $998\,244\,353$ 的倍数。

输出格式

对于每组数据，输出一行一个正整数，表示答案对 $998\,244\,353$ 取模的结果。

样例

样例输入 1

3
1 0
1 1
2 1

样例输出 1

0
0
1