#include<bits/stdc++.h>
#define Yukinoshita namespace
#define Yukino std
#define int long long
using Yukinoshita Yukino;
int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') w=ch=='-'?-1:1,ch=getchar();
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
/*
998244352 1048576 3
*/
signed main()
{
	int p=read(),q=read(),k=read(),i;
	while(k--)
	{
		int a=read()%p,b=read()%p;
		if(p==q)
		{
			putchar('1');
			continue;
		}
		if(__gcd(__gcd(a,b),p)!=q&&__gcd(__gcd(a,b),p)%q==0)
		{
			putchar('0');
			continue;	
		}
		set<int> st{a};
		for(;;)
		{
			a=(1ll*a*a+b)%p;
			if(st.size()>2000)
			{
				putchar('1');
				break;
			}
			if(st.count(a))
			{
				putchar('0');
				break;
			}
			for(auto x:st)
				if(__gcd((a-x+p)%p,p)==q)
				{
					putchar('1');
					goto bre;
				}
//			cout<<a<<',';
			st.insert(a);
		}
		bre:;
//		puts("");	
	}
}