P4616 [COCI 2017/2018 #5] Pictionary

在宇宙一个不为人知的地方，有一个星球，上面有一个国家，只有数学家居住。在这个国家有 $n$ 个数学家，有趣的是，每个数学家都住在自己的城市，且城市间无道路相连，因为他们可以在线交流。当然，城市有从 $1$ 到 $n$ 的编号。 一位数学家决定用手机发论文，而手机将“不言而喻”自动更正成了“猜谜游戏”。不久之后，这个国家就发现了猜谜游戏。他们想要见面一起玩，于是这个国家就开始了修路工程。道路修建会持续 $m$ 天。对于第 $i$ 天，若 $\gcd(a,b)=m-i+1$，则 $a$ 和 $b$ 城市间会修一条路。 由于数学家们忙于建筑工作，请你来确定一对数学家最早什么时候能凑到一起玩。

第一行有三个正整数 $n,m,q$，表示城市数量、修路持续天数、询问数量。 接下来 $q$ 行，每行有两个正整数 $a,b$，表示询问 $a$ 和 $b$ 两个城市的数学家最早什么时候能在一起玩。

输出 $q$ 行，第 $i$ 行有一个正整数，表示第 $i$ 次询问的结果。

对于 $40\%$ 的数据： $n≤4000,q≤10^5$ 对于全部数据： $1≤n,q≤10^5$ $1≤m≤n$ 样例 1 解释： 在第一天，$(3,6)$ 之间修了一条路，因此第二次询问输出 `1`； 在第二天，$(2,4),(2,6),(2,8),(4,6),(6,8)$ 之间都修了一条路，此时 $4$ 和 $8$ 号城市连通，第三次询问输出 `2`； 在第三天，所有编号互质的城市之间都修了路，$2$ 和 $5$ 号城市在此时连通，第一次询问输出 `3`。 样例 2 解释： 在第二天，$(20,15)$ 之间修了一条路； 第四天，$(15,9)$ 之间修了一条路； 所以 $20$ 和 $9$ 号城市在第四天连通，输出 `4`。