Soit $f(n, k)$ le nombre de couples d'entiers $(a, b)$ tels que :
- $0 \le a, b < n$.
- $k(a + b) \equiv ab \pmod n$.
Étant donné deux entiers $n$ et $m$, vous devez calculer
$$\sum_{k=0}^{m} f(n, k)$$
Comme la réponse peut être grande, affichez-la modulo $998\,244\,353$.
Entrée
Il y a plusieurs cas de test. La première ligne de l'entrée contient un entier $T$ ($1 \le T \le 10^4$), indiquant le nombre de cas de test. Pour chaque cas de test :
L'unique ligne contient deux entiers $n$ et $m$ ($1 \le n \le 10^{14}, 0 \le m < n$).
Il est garanti qu'il y a au plus $10$ cas de test avec $n$ supérieur à $10^8$.
Sortie
Pour chaque cas de test, affichez une ligne contenant un entier, indiquant la réponse modulo $998\,244\,353$.
Exemples
Exemple d'entrée 1
4 7 2 100 15 202604 11 1145141 919810
Exemple de sortie 1
25 2500 3444208 165721266