#include<bits/stdc++.h>
using namespace std;

int n,q,s,t;
int Min;

int gcd(int a,int b){
	if(b == 0) return a;
	else return gcd(b,a%b);
}
int main(){
	cin>>n>>q;
	int m;
	while(q--){
		scanf("%d %d",&s,&t);
		if(s > t){
			m = t;
			t = s;
			s = m;
		}
		Min = t-s;
		if(s > 1){
			Min = min(gcd(s+1,t)+1,Min);
			Min = min(gcd(s-1,t)+1,Min);
			Min = min(gcd(s,t+1)+1,Min);
			Min = min(gcd(s,t-1)+1,Min);	
		}
		printf("%d\n",Min);
	}
	return 0;
}