CF1334E.Divisor Paths

You are given a positive integer $D$. Let's build the following graph from it:

• each vertex is a divisor of $D$ (not necessarily prime, $1$ and $D$ itself are also included);
• two vertices $x$ and $y$ ($x \gt y$) have an undirected edge between them if $x$ is divisible by $y$ and $\frac x y$ is a prime;
• the weight of an edge is the number of divisors of $x$ that are not divisors of $y$.

For example, here is the graph for $D=12$:

Edge $(4,12)$ has weight $3$ because $12$ has divisors $[1,2,3,4,6,12]$ and $4$ has divisors $[1,2,4]$. Thus, there are $3$ divisors of $12$ that are not divisors of $4$ — $[3,6,12]$.

There is no edge between $3$ and $2$ because $3$ is not divisible by $2$. There is no edge between $12$ and $3$ because $\frac{12}{3}=4$ is not a prime.

Let the length of the path between some vertices $v$ and $u$ in the graph be the total weight of edges on it. For example, path $[(1, 2), (2, 6), (6, 12), (12, 4), (4, 2), (2, 6)]$ has length $1+2+2+3+1+2=11$. The empty path has length $0$.

So the shortest path between two vertices $v$ and $u$ is the path that has the minimal possible length.

Two paths $a$ and $b$ are different if there is either a different number of edges in them or there is a position $i$ such that $a_i$ and $b_i$ are different edges.

You are given $q$ queries of the following form:

• $v$ $u$ — calculate the number of the shortest paths between vertices $v$ and $u$.

The answer for each query might be large so print it modulo $998244353$.

给你一个正整数 $D$。我们从它构造如下图：

• 每个顶点是 $D$ 的一个约数（不一定是质数，$1$ 和 $D$ 本身也包含在内）；
• 两个顶点 $x$ 和 $y$（其中 $x > y$）之间存在一条无向边，当且仅当 $x$ 被 $y$ 整除，且 $\frac{x}{y}$ 是一个质数；
• 边的权重定义为：$x$ 的约数中不是 $y$ 的约数的个数。

例如，下图是 $D = 12$ 对应的图：

边 $(4,12)$ 的权重为 $3$，因为 $12$ 的约数为 $[1,2,3,4,6,12]$，而 $4$ 的约数为 $[1,2,4]$，因此 $12$ 的约数中不属于 $4$ 的约数有 $3$ 个——即 $[3,6,12]$。

顶点 $3$ 和 $2$ 之间没有边，因为 $3$ 不被 $2$ 整除；顶点 $12$ 和 $3$ 之间也没有边，因为 $\frac{12}{3} = 4$ 不是质数。

定义图中某两个顶点 $v$ 和 $u$ 之间一条路径的长度为该路径上所有边的权重之和。例如，路径 $[(1, 2), (2, 6), (6, 12), (12, 4), (4, 2), (2, 6)]$ 的长度为 $1+2+2+3+1+2 = 11$。空路径的长度为 $0$。

因此，顶点 $v$ 和 $u$ 之间的最短路径是指所有路径中长度最小者。

若两条路径 $a$ 和 $b$ 满足以下任一条件，则称它们不同：

• 它们包含的边数不同；
• 存在某个位置 $i$，使得 $a_i$ 和 $b_i$ 表示不同的边。

你将收到 $q$ 个如下形式的查询：

• $v$ $u$ —— 计算顶点 $v$ 和 $u$ 之间最短路径的条数。

每个查询的答案可能很大，请对 $998244353$ 取模后输出。

The first line contains a single integer $D$ ($1 \le D \le 10^{15}$) — the number the graph is built from.

The second line contains a single integer $q$ ($1 \le q \le 3 \cdot 10^5$) — the number of queries.

Each of the next $q$ lines contains two integers $v$ and $u$ ($1 \le v, u \le D$). It is guaranteed that $D$ is divisible by both $v$ and $u$ (both $v$ and $u$ are divisors of $D$).

第一行包含一个整数 $D$（$1 \le D \le 10^{15}$）—— 图所基于的数。

第二行包含一个整数 $q$（$1 \le q \le 3 \cdot 10^5$）—— 查询次数。

接下来的 $q$ 行中，每行包含两个整数 $v$ 和 $u$（$1 \le v, u \le D$）。保证 $D$ 同时被 $v$ 和 $u$ 整除（即 $v$ 和 $u$ 均为 $D$ 的约数）。

Print $q$ integers — for each query output the number of the shortest paths between the two given vertices modulo $998244353$.

输出 $q$ 个整数——对每个查询，输出两个给定顶点之间最短路径的数量对 $998244353$ 取模的结果。

In the first example:

• The first query is only the empty path — length $0$;
• The second query are paths $[(12, 4), (4, 2), (2, 1)]$ (length $3+1+1=5$), $[(12, 6), (6, 2), (2, 1)]$ (length $2+2+1=5$) and $[(12, 6), (6, 3), (3, 1)]$ (length $2+2+1=5$).
• The third query is only the path $[(3, 1), (1, 2), (2, 4)]$ (length $1+1+1=3$).

在第一个例子中：

• 第一个查询仅包含空路径——长度为 $0$；
• 第二个查询包含路径 $[(12, 4), (4, 2), (2, 1)]$（长度 $3+1+1=5$）、$[(12, 6), (6, 2), (2, 1)]$（长度 $2+2+1=5$）以及 $[(12, 6), (6, 3), (3, 1)]$（长度 $2+2+1=5$）；
• 第三个查询仅包含路径 $[(3, 1), (1, 2), (2, 4)]$（长度 $1+1+1=3$）。