Đường đi trên đồ thị ước

Cho số nguyên dương $D$. Xây dựng đồ thị vô hướng có trọng số như sau:

• Mỗi đỉnh là một ước của $D$ (kể cả $1$ và chính $D$).
• Hai đỉnh $x$ và $y$ (với $x>y$) được nối bằng một cạnh khi $x$ chia hết cho $y$ và $\frac{x}{y}$ là số nguyên tố.
• Trọng số cạnh nối $x$ và $y$ bằng số ước của $x$ mà không phải ước của $y$.

Ví dụ, cạnh giữa $4$ và $12$ có trọng số $3$, vì $12$ có các ước $[1,2,3,4,6,12]$ còn $4$ có các ước $[1,2,4]$, nên có $3$ ước của $12$ không phải ước của $4$ — đó là $[3,6,12]$.

Độ dài của một đường đi giữa hai đỉnh là tổng trọng số các cạnh trên đường đi đó (đường đi có thể đi qua một đỉnh nhiều lần; đường đi rỗng có độ dài $0$). Đường đi ngắn nhất giữa hai đỉnh là đường đi có độ dài nhỏ nhất.

Hai đường đi được coi là khác nhau nếu chúng có số cạnh khác nhau, hoặc tồn tại vị trí $i$ sao cho cạnh thứ $i$ của chúng khác nhau.

Có $q$ truy vấn, mỗi truy vấn cho hai đỉnh $v$ và $u$ — hãy đếm số đường đi ngắn nhất giữa $v$ và $u$. Vì kết quả có thể lớn, in ra theo modulo $998244353$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $D$ $(1\le D\le {10}^{15})$.
• Dòng thứ hai chứa số nguyên $q$ $(1\le q\le 3·{10}^5)$ — số truy vấn.
• $q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $v$ và $u$ $(1\le v,u\le D)$. Bảo đảm $D$ chia hết cho cả $v$ và $u$.

Dữ liệu ra

In ra $q$ dòng, dòng thứ $i$ là số đường đi ngắn nhất giữa $v_i$ và $u_i$, theo modulo $998244353$.

Ràng buộc

• $1\le D\le {10}^{15}$
• $1\le q\le 3·{10}^5$
• $1\le v,u\le D$ và $D$ chia hết cho cả $v$ và $u$

Ví dụ