Niech $f(n, k)$ oznacza liczbę par liczb całkowitych $(a, b)$ takich, że:

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

Mając dane dwie liczby całkowite $n$ oraz $m$, musisz obliczyć

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

Ponieważ odpowiedź może być duża, wypisz ją modulo $998\,244\,353$.

Wejście

Wejście składa się z wielu przypadków testowych. Pierwszy wiersz wejścia zawiera liczbę całkowitą $T$ ($1 \le T \le 10^4$), oznaczającą liczbę przypadków testowych. Dla każdego przypadku testowego:

Jedyny wiersz zawiera dwie liczby całkowite $n$ oraz $m$ ($1 \le n \le 10^{14}, 0 \le m < n$).

Gwarantowane jest, że występuje co najwyżej $10$ przypadków testowych, w których $n$ jest większe niż $10^8$.

Wyjście

Dla każdego przypadku testowego wypisz jeden wiersz zawierający liczbę całkowitą, oznaczającą odpowiedź modulo $998\,244\,353$.

Przykłady

Przykładowe wejście 1

4
7 2
100 15
202604 11
1145141 919810

Przykładowe wyjście 1

25
2500
3444208
165721266