#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <set> 
using namespace std;
int i,j,t;
int gcd(int a,int b)
{
	int x,y;
	if(a>b)
		swap(a,b);
	while(1)
	{
		x=b%a;
		if(x==0)
		{
			return a;
		}
		else
		b=a;
		a=x;
	}
}
int main()
{
	int n,q,a,b;
	scanf("%d %d",&n,&q);
	while(q--)                  
	{
		scanf("%d %d",&a,&b);
		if(a>b)
			swap(a,b);
		t=gcd(a,b);
		int z=9999;
		if((a%2==1&&b%2==0)||(a%2==0&&b%2==1))
			z=2;
		if(a%2==1&&b%2==1)
		{
			z=2;
		}
		if(b%2==0&&a%2==0&&((b/a>=4)||(b-a>=4)))
			z=2;
		if(a==2)
			z=2;
		int mina;
		mina=min(z,t);
		mina=min(mina,abs(a-b));
		printf("%d\n",mina);
	}
}