Pictionary

时间限制1.50s

内存限制125.00MB

题目描述

在宇宙一个不为人知的地方，有一个星球，上面有一个国家，只有数学家居住。 在这个国家有$n$个数学家，有趣的是，每个数学家都住在自己的城市，且城市间无道路相连，因为他们可以在线交流。当然，城市有从$1$到$n$的编号。

一位数学家决定用手机发论文，而手机将“不言而喻”自动更正成了“猜谜游戏”。 不久之后，这个国家就发现了猜谜游戏。他们想要见面一起玩，于是这个国家就开始了修路工程。 道路修建会持续$m$天。对于第$i$天，若$\gcd(a,b)=m-i+1$，则$a$和$b$城市间会修一条路。

由于数学家们忙于建筑工作，请你来确定一对数学家最早什么时候能凑到一起玩。

输入格式

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

输出格式

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

说明

输入输出样例 #1

输入 #1

8 3 3
2 5
3 6
4 8

输出 #1

3
1
2

输入输出样例 #2

输入 #2

25 6 1
20 9

输出 #2

4

输入输出样例 #3

输入 #3

9999 2222 2
1025 2405
3154 8949

输出 #3

1980
2160

说明/提示

对于$40\%$的数据：$n≤4000,q≤10^5$
对于$100\%$的数据： $1≤n,q≤10^5,1≤m≤n$