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

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

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

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

【数据范围】

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

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