4244: 城市最短距离
内存限制：64 MB
时间限制：1 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：397
通过：74
题目描述
已知现在有n个城市，城市以1到n进行编号，不同城市之间的距离为两城市编号的最大公约数。
求城市 x 到城市 y 的所需移动的最短距离。
求城市 x 到城市 y 的所需移动的最短距离。
输入格式
第一行两个数n，q。表示有n个城市，q组询问。
接下来q行，每行两个数x，y。
接下来q行，每行两个数x，y。
输出格式
每个询问输出一行，每行一个数字表示答案。
输入样例 复制
5 2
1 1
2 4输出样例 复制
0
2数据范围与提示
1 ≤ n ≤ 107, 1 ≤ q ≤ 5 ∗ 105
1 ≤ x, y ≤ n, 1 ≤ x, y ≤ n
1 ≤ x, y ≤ n, 1 ≤ x, y ≤ n