温馨提示

本题时限为 std 的两倍。

题目描述

坎格鲁斯普雷给了你一个有 $n$ 个节点的无向图。

在图中，若点 $i$ 和点 $j$ 之间存在一条边权为 $1$ 的无向边，当且仅当 $\frac{max(i,j)}{min(i,j)}$ 是质数（只有整数才是质数）。

现在，坎格鲁斯普雷向你提出了 $q$ 个询问，每次询问询问 $x$ , $y$ 两点之间的最短路长度。若点 $x$ 和点 $y$ 不联通，输出 "-1"（不含引号）。

输入格式

输入第一行两个整数 $n$ , $q$ 。 $(1 \leq n \leq 10^{12},1 \leq q \leq 1000)$

接下来 $q$ 行，每行两个整数 $x$ , $y$ ,表示一次询问。 $(1 \leq x,y \leq n)$

输出格式

对于每个询问，输出一行一个整数表示答案。若点 $x$ 和点 $y$ 不联通，输出 "-1"（不含引号）。

输入输出样例

输入 #1

15 2
1 6
15 4

输出 #1

2
4

输入 #2

1000000000000 1
114514 1919810

输出 #2

6

说明与提示

对于样例 #1:

对于第一次询问，其中一条最短路为 $1 \xrightarrow{} 2 \xrightarrow{} 6$ ，可以证明，不存在更短的路径。

对于第二次询问，其中一条最短路为 $15 \xrightarrow{} 5 \xrightarrow{} 10 \xrightarrow{} 2 \xrightarrow{} 4$ ，可以证明，不存在更短的路径。