小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的最短路径的距离。