小Q有一张无向图$G = <V, E>$，这个图一共有$n$个点，并且对于每一对点$(i, j)$来说，都有一条边$e(i, j) = gcd(i, j)$。
它想询问您$q$次，每次询问给出一点对$(s, t)$，它想知道$s \rightarrow t$的最短路径的距离。
图：
图(Graph)是由两个集合构成，一个是非空但是有限的顶点集合$V$,另一个是描述结合间的关系边的集合$E$,因此图可以表示为$G=<V, E>$.每条边是一对顶点$(v,w)$且 $v,w \in V$.通常$|V|$和$|E|$表示顶点个数和边的数量。值得注意的是图中顶点一定不能为空，而边可以为空。
无向图：
无向图是指图中的边没有方向性即边$(v,w)$与边$(w,v)$是同一条边。用圆括号"( )"来表示无向边。
单组数据评测。
第一行两个正整数$n, q(2 \leq n, q \leq 10^5)$，表示图中有$n$个点以及$q$次询问。
接下来$q$行，每行两个正整数$s_i, t_i(1 \leq s_i, t_i \leq n, s_i \neq t_i)$，表示它想知道$s_i \rightarrow t_i$的最短路径的距离。
输出包含$q$行，每行一个正整数表示$s_i \rightarrow t_i$的最短路径的距离。