#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<stdlib.h>
#include<math.h>
#include<map>
#include<set>
#include<queue>
#include<vector>
using namespace std;
int prime[100020],r[100020]={0};
void p(void){
	for(int i=1;i<=100025;i++){
		prime[i]=1;
	}
	for(int i=2;i<=100020;i++){
		for(int j=2;i*j<=100025;j++){
			prime[i*j]=0;
		}
	}
}
int gcd(int x,int y){
	if(x==y) return x;
	else if(x>y){
		if(x%y!=0){
			int w=x/y;return gcd(x-w*y,y);
		}else return gcd(y,y);
		
	}else{
		if(y%x!=0){
			int w=y/x;return gcd(x,y-w*x);
		}else{
			return gcd(x,x);
		} 
	} 
}
int main()
{
	int T,x,y,n,q;
	p();
	for(int i=1;i<=100025;i++){
		if(prime[i]==1) r[i]=r[i-1]+1;
		else r[i]=r[i-1];
	}
	scanf("%d %d",&n,&q);
	for(int i=1;i<=q;i++){
		scanf("%d %d",&x,&y);
		if(prime[x]==1&&prime[y]==1) printf("1\n");
		else if(r[y-1]-r[x]>=1) printf("2\n");
		else printf("%d\n",gcd(x,y));
	}
	//printf("%d\n",rank[8]);
	
}