La $f(n, k)$ være antallet heltallspar $(a, b)$ slik at:

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

Gitt to heltall $n$ og $m$, må du beregne

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

Siden svaret kan være stort, skriv det ut modulo $998\,244\,353$.

Inndata

Det er flere testtilfeller. Den første linjen i inndataene inneholder et heltall $T$ ($1 \le T \le 10^4$), som angir antallet testtilfeller. For hvert testtilfelle:

Den eneste linjen inneholder to heltall $n$ og $m$ ($1 \le n \le 10^{14}, 0 \le m < n$).

Det er garantert at det er høyst $10$ testtilfeller med $n$ større enn $10^8$.

Utdata

For hvert testtilfelle, skriv ut én linje som inneholder ett heltall, som angir svaret modulo $998\,244\,353$.

Eksempler

Eksempelinndata 1

4
7 2
100 15
202604 11
1145141 919810

Eksempelutdata 1

25
2500
3444208
165721266