#include<bits/stdc++.h>
#define Yukinoshita namespace
#define Yukino std
#define int unsigned 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;
}
vector<int> t[1<<20];
/*
gcd(a-b,P)=Q
*/
signed main()
{
	int p=read(),q=read(),k=read();
	while(k--)
	{
		int a=read()%p,b=read()%p,i;
		for(i=0;i<q;i++)
			t[i].clear();
//		cout<<a<<' '<<b<<' '<<q<<endl;
		int g=__gcd(p,__gcd(a,b));
		if(g!=q&&g%q==0)
		{
			putchar('0');
			continue;
		}
		t[a%q].push_back(a);
		for(int T=0;T<q/__gcd(a,b);T++)
		{
			a=(a*a+b)%p;
			int w=a%q;
		//	cout<<a<<endl;
//			cout<<':'<<a<<endl;
			for(auto x:t[w])
			{
				if(__gcd(p,(p-x+a)%p)==q)
				{
					putchar('1');
					goto bre;
				}
				if(x==a)
				{
					putchar('0');
					goto bre;
				}
			}
//			cout<<t[w].size()<<endl;
			t[w].push_back(a);
		}
		putchar('0');
		bre:;
	}
}
/*
100237 100237 10
11178595626727644735 679276059713497324
*/