Description

有一张包含 $n$ 个点的图，点编号为 $1,2\dots n$ 。对于点 $1 \le i < j \le n$ 之间存在一条边权为 $GCD(i,j)$ 的双向边，即边权为 $i,j$ 的最大公约数。有 $q$ 组询问，每组询问给出 $u, v$ 两点，请回答 $u,v$ 之间的最短距离及最短路径数。最短路径数可能很大，结果请对 $998244353$ 取模。

Input Format

第一行输入两个整数 $n, q( 2\le n \le 10^7, 1 \le q \le 50000)$，含义与题面描述一致。接下来 $q$ 行，每行输入两个整数 $u,v(1\le u,v\le n, u \ne v)$，含义与题面描述一致。

Output Format

对于每个询问，在单独的一行输出两个整数，之间用一个空格隔开，第一个整数为 $u,v$ 之间的最短距离，第二个整数为 $u,v$ 之间的最短路径数。

6 2
4 5
3 6

1 1
2 2

Source

Online Judge http://127.0.0.1