Låt $f(n, k)$ vara antalet heltalspar $(a, b)$ sådana att:

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

Givet två heltal $n$ och $m$ ska du beräkna

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

Eftersom svaret kan vara stort, skriv ut det modulo $998\,244\,353$.

Indata

Det finns flera testfall. Den första raden i indata innehåller ett heltal $T$ ($1 \le T \le 10^4$), som anger antalet testfall. För varje testfall:

Den enda raden innehåller två heltal $n$ och $m$ ($1 \le n \le 10^{14}, 0 \le m < n$).

Det garanteras att det finns högst $10$ testfall där $n$ är större än $10^8$.

Utdata

För varje testfall, skriv ut en rad som innehåller ett heltal, vilket anger svaret modulo $998\,244\,353$.

Exempel

Exempelindata 1

4
7 2
100 15
202604 11
1145141 919810

Exempelutdata 1

25
2500
3444208
165721266