#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;
const int maxn = 10005;
const int inf = 0x3f3f3f3f;
int n,m,t,p,q;
int a[maxn],b[maxn];
int mp[maxn][maxn];
int gcd(int a,int b){
	int z=b;
	while(a%b!=0){
		z=a%b;
		a=b;
		b=z;
	}
	return z;
}
void flo(){
	for(int k=1;k<=n;k++){
		for(int i=k+1;i<=n;i++){
			for(int j=i+1;j<=n;j++){
				mp[i][j]=min(mp[i][j],mp[k][i]+mp[k][j]);
			}
		}
	}
}
int check(int x){
	for(int i=2;i*i<=x;i++){
		if(x%i==0) return 0;
	}
	return 1;
}
int main(){
	memset(mp,0,sizeof(mp));
    scanf("%d %d",&n,&t);
	for(int i=2;i<=n;i++){
		b[i]=check(i);
		if(b[i]) a[i]=a[i-1]+1;
		else a[i]=a[i-1];
	}
	for(int i=0;i<t;i++){
		scanf("%d %d",&p,&q);
		if(p>q) {
			int temp=p;
			p=q;
			q=temp;
		}
		if(gcd(q,p)==1){
			printf("1\n");
		}
		else{
			if((a[q]-a[p]+b[i])==0) printf("%d\n",gcd(q,p));
			else printf("2\n");
		}
	}
}