Sia $f(n, k)$ il numero di coppie di interi $(a, b)$ tali che:

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

Dati due interi $n$ e $m$, devi calcolare

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

Poiché la risposta può essere grande, stampala modulo $998\,244\,353$.

Input

Ci sono più casi di test. La prima riga dell'input contiene un intero $T$ ($1 \le T \le 10^4$), che indica il numero di casi di test. Per ciascun caso di test:

L'unica riga contiene due interi $n$ e $m$ ($1 \le n \le 10^{14}, 0 \le m < n$).

È garantito che ci sono al massimo $10$ casi di test con $n$ maggiore di $10^8$.

Output

Per ciascun caso di test, stampa una riga contenente un intero, che indica la risposta modulo $998\,244\,353$.

Esempi

Input di esempio 1

4
7 2
100 15
202604 11
1145141 919810

Output di esempio 1

25
2500
3444208
165721266