E. 除数路径
每个测试的时间限制：$3$ 秒
内存限制：$256$ MB

给定一个正整数 $D$。我们基于它构建如下无向图：

• 每个顶点是 $D$ 的一个正因子（不一定是素数，$1$ 和 $D$ 本身也包括在内）；
• 两个顶点 $x$ 和 $y$（$x > y$）之间有一条无向边，当且仅当 $x$ 被 $y$ 整除且 $x / y$ 是素数；
• 边的权值定义为 $x$ 的因子个数减去 $y$ 的因子个数，即 $x$ 的因子中不是 $y$ 的因子的个数。

例如，$D = 12$ 的图如下所示（图略）。
边 $(4,12)$ 的权值为 $3$，因为 $12$ 的因子集合为 $\{1,2,3,4,6,12\}$，$4$ 的因子集合为 $\{1,2,4\}$，所以 $12$ 的因子中有 $3$ 个不是 $4$ 的因子：$\{3,6,12\}$。

$3$ 和 $2$ 之间没有边，因为 $3$ 不能被 $2$ 整除。$12$ 和 $3$ 之间也没有边，因为 $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$ 使得第 $i$ 条边 $a_i$ 与 $b_i$ 不同。

给定 $q$ 个询问，每个询问的形式为：

$v$ $u$ —— 计算顶点 $v$ 和 $u$ 之间的最短路径的数量，结果对 $998244353$ 取模。

---

输入

第一行一个整数 $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$ 的因子）。

输出

输出 $q$ 行，每行一个整数 —— 对应询问的答案模 $998244353$。

---

样例

样例输入1

12
3
4 4
12 1
3 4

样例输出1

1
3
1

样例输入2

1
1
1 1

样例输出2

1

样例输入3

288807105787200
4
46 482955026400
12556830686400 897
414 12556830686400
4443186242880 325

样例输出3

547558588
277147129
457421435
702277623

---