Нехай $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