Source : 中山纪念中学宋新波老师
Description

有n个城市,标号为1到n,第i天时,若gcd(a,b)=m-i+1,则标号为a的城市和标号为b的城市会建好一条直接相连的道路,有多次询问,每次询问某两座城市最早什么时候能连通。

Input

第一行输入三个正整数n,m,q,其中q表示询问个数。

接下来q行,每行两个正整数x,y,表示询问城市x和城市y最早什么时候连通。

Output

输出q行,每行一个正整数,表示最早连通是第几天。

Sample Input 1
8 3 3
2 5
3 6
4 8
Sample Output 1
3
1
2
Sample Input 2
25 6 1
20 9
Sample Output 2
4
Sample Input 3
9999 2222 2
1025 2405
3154 8949
Sample Output 3
1980
2160
Hint

【数据范围】

对于40%的数据,1<=n<=1000。

对于100%的数据,1<=n,q≤ 100000,1<=m<=q。