8656: Shortest Path in GCD Graph

There is an edge-weighted complete graph Kn with $n$ vertices, where vertices are labeled through $1,2,...,n$. For each $1\le i<j\le n$, the weight of the edge (i,j) between i and j is $)$, the greatest common divisor of i and j.

You need to answer q queries. In each query, given two vertices u,v, you need to answer the length of the shortest path as well as the number of shortest paths between u,v. Since the number of shortest paths may be too large, you only need to output it modulo 998244353

The first line contains two integers n,q(2≤n≤107,1≤q≤50000), denoting the number vertices in the graph and the number of queries, respectively.

Then q lines follow, where each line contains two integers $u,v(1\le u,v\le n,u！=v)$, denoting a query between u and v.