Sei $f(n, k)$ die Anzahl der ganzzahligen Paare $(a, b)$, sodass gilt:

• $0 \le a, b < n$.
• $k(a + b) \equiv ab \pmod n$.

Gegeben zwei ganze Zahlen $n$ und $m$, müssen Sie Folgendes berechnen:

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

Da die Antwort groß sein kann, geben Sie diese modulo $998\,244\,353$ aus.

Eingabe

Es gibt mehrere Testfälle. Die erste Zeile der Eingabe enthält eine ganze Zahl $T$ ($1 \le T \le 10^4$), die die Anzahl der Testfälle angibt. Für jeden Testfall gilt:

Die einzige Zeile enthält zwei ganze Zahlen $n$ und $m$ ($1 \le n \le 10^{14}, 0 \le m < n$).

Es wird garantiert, dass es höchstens $10$ Testfälle gibt, bei denen $n$ größer als $10^8$ ist.

Ausgabe

Geben Sie für jeden Testfall eine Zeile mit einer ganzen Zahl aus, die die Antwort modulo $998\,244\,353$ angibt.

Beispiele

Beispieleingabe 1

4
7 2
100 15
202604 11
1145141 919810

Beispielausgabe 1

25
2500
3444208
165721266