#include<stdio.h>
int gcd(int m,int n)
{
int temp;
if(n>m)
{
temp=n;
n=m;
m=temp;
}
if(m%n==0)
return n;
else
return gcd(m-n,n);
}
int main()
{
int n,q,si,ti;
scanf("%d%d",&n,&q);
while(q--)
{
scanf("%d%d",&si,&ti);
if(gcd(si,ti)==1)
printf("1\n");
else
printf("2\n");
}
}