$f(n,k)$ を、次の条件を満たす整数の組 $(a,b)$ の数とする：

• $0 \le a,b < n$.

• $k(a+b) \equiv ab \pmod n$.

2 個の整数 $n$ と $m$ が与えられる。次の値を計算せよ：

$$\sum_{k=0}^{m} f(n,k)$$

答えは大きくなる可能性があるので、$998\,244\,353$ で割った余りを出力せよ。

入力

複数のテストケースがある。入力の最初の行には、テストケースの数を表す整数 $T$ が与えられる ($1 \le T \le 10^4$)。各テストケースについて：

唯一の行には 2 個の整数 $n$ と $m$ が与えられる ($1 \le n \le 10^{14}$, $0 \le m < n$)。

$n$ が $10^8$ より大きいテストケースは高々 10 個であることが保証される。

出力

各テストケースについて、答えを $998\,244\,353$ で割った余りを表す整数を 1 行に 1 つ出力せよ。

入出力例

入力 1

4
7 2
100 15
202604 11
1145141 919810

出力 1

25
2500
3444208
165721266