给你一个正整数$$$D$$$。让我们根据它构建以下图表:
- 每个顶点都是 $$$D$$$ 的约数(不一定是素数,$$$1$$$ 和 $$$D$$$ 本身也包括在内);
- 如果 $$$x$$$ 可被 $$$y$$$ 整除且 $$$\frac 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$$$ 之间没有边,因为 $$$\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$$$ 模。
输入
第一行包含一个整数 $$$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
注意
在第一个示例中:
- 第一个查询只是空路径 — 长度 $$$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$$$)。