#include <bits/stdc++.h>
#define lowbit(x) (x&(-x))
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
using namespace std;
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
int main()
{
int n,q;
int u,v;
scanf("%d%d",&n,&q);
for(int i=0;i<q;++i)
{
scanf("%d%d",&u,&v);
if(gcd(u,v)==1)
puts("1");
else
puts("2");
}
return 0;
}