Gọi $f(n, k)$ là số lượng cặp số nguyên $(a, b)$ sao cho:

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

Cho hai số nguyên $n$ và $m$, bạn cần tính:

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

Vì đáp án có thể rất lớn, hãy in ra kết quả theo modulo $998\,244\,353$.

Dữ liệu vào

Có nhiều bộ dữ liệu. Dòng đầu tiên của dữ liệu vào chứa một số nguyên $T$ ($1 \le T \le 10^4$), cho biết số lượng bộ dữ liệu. Với mỗi bộ dữ liệu:

Dòng duy nhất chứa hai số nguyên $n$ và $m$ ($1 \le n \le 10^{14}, 0 \le m < n$).

Đảm bảo rằng có nhiều nhất $10$ bộ dữ liệu có $n$ lớn hơn $10^8$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một dòng chứa một số nguyên, cho biết đáp án theo modulo $998\,244\,353$.

Ví dụ

Dữ liệu vào 1

4
7 2
100 15
202604 11
1145141 919810

Dữ liệu ra 1

25
2500
3444208
165721266