#1167. zxh的高考幸运法阵

今天是高考的日子! Sheauhaw 决定通过一系列神秘活动为考生祈福, 于是在操场上画出了一个奇怪的图案:

你百思不得其解, Sheauhaw 向你解释的这个图的意义: 今天的考试的幸运数字是 $D$, 于是就可以画一个基于 $D$ 的幸运法阵. 它是这样制作的:

1. 首先生成节点: 法阵中的每个节点都是 $D$ 的正因子. 显然, 节点不要求是素数, $1$ 和 $D$ 也是节点.
2. 之后生成边: 法阵中的任意两个节点 $x,y$ ($x>y$), 若满足 $y\mid x$ 且 $x/y$ 是素数, 那么就会在 $x$ 和 $y$ 之间生成一条无向边.
3. 最后赋予边权: 连接 $x,y$ ($x>y$) 的边的权值是 $x$ 相对于 $y$ 的特有因子个数. 一个数 $d$ 如果是 $x$ 的因子, 但不是 $y$ 的因子, 那么 $d$ 就是一个 $x$ 相对于 $y$ 的特有因子.

例如, 你看到的奇怪图案就是 $D=12$ 生成的幸运法阵. 你会发现:

1. $(4,12)$ 这条边的权值是 $3$. 因为 $12$ 的因子有 $\{1,2,3,4,6,12\}$, $4$ 的因子有 $\{1,2,4\}$, 于是 $12$ 相对于 $4$ 的特有因子有 $3$ 个, 分别是 $\{3,6,12\}$.
2. $3$ 和 $2$ 之间没有边直接连接, 因为 $2\nmid 3$.
3. $12$ 和 $3$ 之间没有边直接连接, 因为 $12/3=4$ 不是素数.

Sheauhaw 解释完这个图的构造后, 说明了这个法阵的应用: 法阵上的两个数字指导着两个行为, 这两个数字之间的关系就尤为重要. Sheauhaw 定义了法阵上两个数字的默契值: 如果 $x,y$ 是图上的两个节点, 那么这两点之间最短路的个数称为 $x,y$ 之间的默契值 $C(x,y)$.

由于 Sheauhaw 的幸运占卜计算量极其庞大, 他请你帮他计算 $q$ 组节点的默契值. 由于数字可能比较大, 他只需要默契值对 $919,260,817$ 取模的值就可以估测两个数字的关系.

第一行两个整数 $D,q$, 分别表示幸运数字和询问次数.

接下来 $q$ 行, 每行两个整数 $x,y$, 表示需要计算的节点.

输出 $q$ 行, 每行输出一个整数 $C$, 表示询问的两节点之间的默契值对 $919,260,817$ 取模的结果.

样例输入

12 3
4 4
12 1
3 4

样例输出

1
3
1

$1\le D\le10^{15}$

$1\le q\le 3\cdot10^5$

$1\le x,y\le D$