Cho một số nguyên dương $m$, chúng ta xác định một đồ thị hai phía không trọng số $G(m)$ với ($2m-2$) đỉnh như sau:

Đồ thị $G(m)$ là một đồ thị vô hướng có thể được tô màu đen và trắng, với $(m-1)$ đỉnh đen và $(m-1)$ đỉnh trắng. Gọi $X$ là tập hợp của tất cả các đỉnh đen và $Y$ là tập hợp của tất cả các đỉnh trắng.

Đặt $i_X$ đại diện cho điểm với số $i$ trong tập $X$, và $i_Y$ đại diện cho điểm với số $i$ trong tập $Y$, với $1 ≤ i ≤ m-1$. Có một cạnh giữa $i_X$ và $j_Y$ khi và chỉ khi ít nhất một trong các điều kiện sau đây thỏa mãn:

• $i = j$
• $i \times j \equiv 1$ $\pmod {m}$.

Đặt $f[G(m)]$ là số lượng các cặp ghép tối đa khác nhau cơ bản trong $G(m)$. Hai cặp ghép được coi là khác nhau cơ bản nếu và chỉ nếu tồn tại $i_X$ sao cho nó được ghép với $j_Y$ trong một cách này và không được ghép với $j_Y$ trong một cách khác.

Cho $q$ nhóm truy vấn, mỗi nhóm chứa hai số nguyên dương $l$ và $r$.
Yêu cầu: với mỗi truy vấn, tìm $\sum_{i=l}^r f[G(i)]$ modulo $998244353$.

5
1 10
5 5
3 4
6 9
10 20

18
2
2
10
455