#include<bits/stdc++.h>
using namespace std;
int jud(int n){
	if(n==1)return 1;
	else if(n==2)return 0;
	for(int i=2;i<=sqrt(n);i++){
		if(n%i==0)return 0;
	}
	return 1;
}
int gcd(int a,int b){
	if(a>b)swap(a,b);
	if(a==b)return 0;
	int maxn=0;
	for(int i=1;i<=a;i++){
		if(a%i==0&&b%i==0)maxn=i;
	}
	return maxn;
}
int main(){
	int n,q;
	scanf("%d%d",&n,&q);
	while(q--){
		int a,b,is=0;
		scanf("%d%d",&a,&b);
		if(a>b)swap(a,b);
		if(abs(a-b)==1)printf("1\n");
		else if(b%a==0)printf("2\n");
		else if(b==a)printf("0\n");
		else if(jud(a)||jud(b))printf("1\n");
		else {
			for(int i=a;i<=b;i++){
				if(jud(i)==1){
					printf("2\n");
					is=1;
					break;
				}
			}
			if(is==0){
				int minn=abs(a-b),cnt;
				for(int i=a;i<=b;i++){
					cnt=gcd(a,i)+gcd(i,b);
					minn=min(cnt,minn);
				}
				printf("%d\n",minn);
			}
		}
	}
	return 0;
}