有一个包含 $n$ 个顶点的完全图 $K_n$，顶点编号为 $1, 2, \dots, n$。对于每个 $1 \le i < j \le n$，边 $(i, j)$ 的权重为 $i$ 和 $j$ 的最大公约数 $\gcd(i, j)$。

你需要回答 $q$ 次询问。每次询问给定两个顶点 $u, v$，你需要回答 $u$ 和 $v$ 之间的最短路径长度以及最短路径的数量。由于最短路径的数量可能非常大，你只需要输出其对 $998244353$ 取模的结果。

输入格式

第一行包含两个整数 $n, q$ ($2 \le n \le 10^7, 1 \le q \le 50000$)，分别表示图中的顶点数和询问次数。

接下来 $q$ 行，每行包含两个整数 $u, v$ ($1 \le u, v \le n, u \neq v$)，表示一次关于 $u$ 和 $v$ 的询问。

输出格式

对于每次询问，输出一行，包含两个整数，分别表示给定节点间的最短路径长度和最短路径数量。注意，只有最短路径数量需要对 $998244353$ 取模。

样例

样例输入 1

6 2
4 5
3 6

样例输出 1

1 1
2 2