Задано целое положительное число $$$D$$$. Построим из него следующий граф:
Например, граф для $$$D=12$$$:
У ребра $$$(4,12)$$$ вес $$$3$$$, потому что у $$$12$$$ делители $$$[1,2,3,4,6,12]$$$, а у $$$4$$$ делители $$$[1,2,4]$$$. Поэтому существует $$$3$$$ делителя $$$12$$$, которые не являются делителями $$$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$$$ запросов вида:
Ответ может быть довольно большим, поэтому выведите его по модулю $$$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$$$.
12 3 4 4 12 1 3 4
1 3 1
1 1 1 1
1
288807105787200 4 46 482955026400 12556830686400 897 414 12556830686400 4443186242880 325
547558588 277147129 457421435 702277623
В первом примере:
