יהי $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