Sea $f(n,k)$ el número de pares de enteros $(a,b)$ tales que:

• $0 \le a,b < n$.

• $k(a+b) \equiv ab \pmod n$.

Dados dos enteros $n$ y $m$, debes calcular

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

Como la respuesta puede ser grande, imprímela módulo $998\,244\,353$.

Entrada

Hay varios casos de prueba. La primera línea de la entrada contiene un entero $T$ ($1 \le T \le 10^4$), que indica el número de casos de prueba. Para cada caso de prueba:

La única línea contiene dos enteros $n$ y $m$ ($1 \le n \le 10^{14}$, $0 \le m < n$).

Se garantiza que hay como máximo 10 casos de prueba con $n$ mayor que $10^8$.

Salida

Para cada caso de prueba, imprime una línea con un entero que represente la respuesta módulo $998\,244\,353$.

Ejemplos

Entrada 1

4
7 2
100 15
202604 11
1145141 919810

Salida 1

25
2500
3444208
165721266