Látum $f(n, k)$ vera fjölda heiltvennda $(a, b)$ þannig að:

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

Gefnar eru tvær heiltölur $n$ og $m$, og þú þarft að reikna

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

Þar sem svarið getur verið stórt skaltu prenta það modulo $998\,244\,353$.

Inntak

Það eru mörg prófunartilvik. Fyrsta línan í inntakinu inniheldur heiltölu $T$ ($1 \le T \le 10^4$), sem gefur til kynna fjölda prófunartilvika. Fyrir hvert prófunartilvik:

Eina línan inniheldur tvær heiltölur $n$ og $m$ ($1 \le n \le 10^{14}, 0 \le m < n$).

Það er tryggt að það séu í mesta lagi $10$ prófunartilvik þar sem $n$ er stærra en $10^8$.

Úttak

Fyrir hvert prófunartilvik skal prenta eina línu sem inniheldur heiltölu, sem gefur til kynna svarið modulo $998\,244\,353$.

Dæmi

Dæmi um inntak 1

4
7 2
100 15
202604 11
1145141 919810

Dæmi um úttak 1

25
2500
3444208
165721266