#include<stdio.h>
#include<math.h>
int gcd(int a,int b)
{
	int r=a%b;
	
	while(r!=0)
	{
		a=b;
		b=r;
		r=a%b;
	}
	
	return b;
}
int min(int a,int b)
{
	return a<b?a:b;
}
int main()
{
	int n,q;
	int s,t;
	int res;
	
	scanf("%d %d",&n,&q);
	
	while(q--)
	{
		res=0;
		scanf("%d %d",&s,&t);
		if(s>t)
		{
			s=s+t;t=s-t;s=s=t;
		}
		
		if(s==1)
		{
			printf("1\n");
			continue;
		}
		else
		{
			res=min(gcd(s,t),2);
			printf("%d\n",res);
			continue;
		}
	}
	return 0;
}