ليكن $f(n, k)$ هو عدد أزواج الأعداد الصحيحة $(a, b)$ بحيث:

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

بإعطائك عددين صحيحين $n$ و $m$، عليك حساب

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

نظراً لأن الإجابة قد تكون كبيرة، اطبعها باقي قسمتها على $998\,244\,353$.

الإدخال

توجد عدة حالات اختبار. السطر الأول من الإدخال يحتوي على عدد صحيح $T$ ($1 \le T \le 10^4$)، يشير إلى عدد حالات الاختبار. لكل حالة اختبار:

السطر الوحيد يحتوي على عددين صحيحين $n$ و $m$ ($1 \le n \le 10^{14}, 0 \le m < n$).

من المضمون أنه توجد على الأكثر $10$ حالات اختبار يكون فيها $n$ أكبر من $10^8$.

الإخراج

لكل حالة اختبار، اطبع سطراً واحداً يحتوي على عدد صحيح، يشير إلى الإجابة باقي قسمتها على $998\,244\,353$.

أمثلة

مثال الإدخال 1

4
7 2
100 15
202604 11
1145141 919810

مثال الإخراج 1

25
2500
3444208
165721266