#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
int gcd(int a,int b){
	if(a%b==0)	return b;
	else	return gcd(b,a%b);
}
int n,q,s,t,x,y,i;
int main(){
	scanf("%d %d",&n,&q);
	while(q--){
		scanf("%d %d",&s,&t);
		if(gcd(s,t)==1)	printf("1\n");
		else{
			for(i=s+1;i<=t-1;i++){
				if(gcd(i,t)==1){
					x=i-s+1;
					break;
				}
			}
			for(i=t-1;i>=s+1;i--){
				if(gcd(i,s)==1){
					y=t-i+1;
					break;
				}
			}
			//printf("%d %d\n",x,y);
			if(x>y)	printf("%d\n",y);
			else	printf("%d\n",x);
		}
	}
}