#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define dep(i,x,y) for(int i=y;i>=x;--i)
using namespace std;
typedef long long ll;
//struct node{
//	int 
//}p[];
//bool cmp(node a,node b)
//{
//	return ;
//}
int n,m,k,x,y,q,a[301010];
char s[101010];
int gcd(int a,int b)
{
	if(b==0) return a;
	return gcd(b,a%b);
}
int main()
{
	scanf("%d%d",&n,&m);
	rep(i,1,m)
	{
		scanf("%d%d",&x,&y);
		printf("%d\n",min(2,gcd(x,y)));
	}
}