Problem Description

There is an edge-weighted complete graph $K_n$ with $n$ vertices, where vertices are labeled through $1,2,...,n$.
For each $1\leq i\lt j\leq n$, the weight of the edge $(i,j)$ between $i$ and $j$ is $gcd(i,j)$, 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 <strong> length of the shortest path</strong> as well as the <strong>number of shortest paths</strong> between $u,v$. Since the <strong>number of shortest paths</strong> may be too large, you only need to output it modulo $998244353$.

Input

The first line contains two integers $n,q(2\leq n \leq 10^7,1\leq q\leq 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\leq u,v\leq n,u\neq v)$, denoting a query between $u$ and $v$.

Output

For each query, output one line contains two integers, denote the length and number of shortest path between given nodes, respectively. Note that only the <strong>number of shortest paths</strong> should be taken modulo $998244353$.

6 2
4 5
3 6

1 1
2 2