Olkoon $f(n, k)$ sellaisten kokonaislukuparien $(a, b)$ lukumäärä, joille:

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

Annetaan kaksi kokonaislukua $n$ ja $m$, ja tehtävänäsi on laskea

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

Koska vastaus voi olla suuri, tulosta se modulo $998\,244\,353$.

Syöte

Syötteessä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 10^4$), joka ilmaisee testitapausten lukumäärän. Jokaiselle testitapaukselle:

Ainoa rivi sisältää kaksi kokonaislukua $n$ ja $m$ ($1 \le n \le 10^{14}, 0 \le m < n$).

On taattu, että on enintään $10$ testitapausta, joissa $n$ on suurempi kuin $10^8$.

Tuloste

Tulosta jokaiselle testitapaukselle yksi rivi, joka sisältää kokonaisluvun, vastauksen modulo $998\,244\,353$.

Esimerkit

Esimerkkisyöte 1

4
7 2
100 15
202604 11
1145141 919810

Esimerkkituloste 1

25
2500
3444208
165721266