#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5;
ll n,m,q,cnt,fa[N+5],dp[N+5][25],w[N+5][25],deep[N+5],lg[N+5];
bool vis[N+5];
struct node
{
	ll u,v,w;
}a[N*20+5];
struct tu
{
	ll v,w;
};
vector <tu> g[N+5];
bool cmp(node x,node y)
{
	return x.w<y.w;
}
ll get(ll x)
{
	if(fa[x]==x) return x;
	return fa[x]=get(fa[x]);
}
void dfs(ll u)
{
	vis[u]=1;
	for(ll i=0;i<g[u].size();i++)
	{
		ll v=g[u][i].v,ww=g[u][i].w;
		if(vis[v]) continue;
		deep[v]=deep[u]+1;
		dp[v][0]=u;
		w[v][0]=ww;	
		dfs(v);
	}
}
void ycl()
{
	for(ll j=1;j<=lg[n];j++)
	{
		for(ll i=1;i<=n;i++)
		{
			dp[i][j]=dp[dp[i][j-1]][j-1];
			w[i][j]=max(w[i][j-1],w[dp[i][j-1]][j-1]);
		}
	}
}
ll LCA(ll x,ll y)
{
	if(get(x)!=get(y)) return -1;
	if(deep[x]>deep[y]) swap(x,y);
	ll ans=0;
	for(ll i=lg[n];i>=0;i--)
	{
		if(deep[dp[y][i]]>=deep[x])
		{
			ans=max(ans,w[y][i]);
			y=dp[y][i];
		}
	}
	if(x==y) return ans;
	for(ll i=lg[n];i>=1;i--)
	{
		if(dp[x][i]!=dp[y][i])
		{
			ans=max(ans,max(w[x][i],w[y][i]));
			x=dp[x][i];
			y=dp[y][i];
		}
	}
	ans=max(ans,max(w[x][0],w[y][0]));
	return ans;
}
int main()
{
	cin>>n>>m;
	for(ll i=1;i<=n;i++) 
	{
		fa[i]=i;
		if(i>=2) lg[i]=lg[i>>1]+1;
	}
	for(ll i=1;i<=m;i++)
	{
		for(ll j=2;j*i<=n;j++)
		{
			cnt++;
			a[cnt].u=(j-1)*i;
			a[cnt].v=j*i;
			a[cnt].w=m-i+1;
		}
	}
	stable_sort(a+1,a+1+cnt,cmp);
	for(ll i=1;i<=cnt;i++)
	{
		ll rx=get(a[i].u),ry=get(a[i].v);
		if(rx==ry) continue;
		fa[ry]=rx;
		g[a[i].u].push_back({a[i].v,a[i].w});
		g[a[i].v].push_back({a[i].u,a[i].w});
	}
	for(ll i=1;i<=n;i++)
	{
		if(!vis[i]) 
		{
			deep[i]=1;
			dfs(i);
			w[i][0]=0;
			dp[i][0]=i;
		}
	}
	ycl();
	cin>>q;
	for(ll i=1;i<=q;i++)
	{
		ll x,y;
		cin>>x>>y;
		cout<<LCA(x,y)<<endl;
	}
	return 0;
}