Пусть $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