#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
ll n,q;
int gcd(ll x,ll y)
{
	if(y%x==0)
	return x;
	else
	{
		for(int i=sqrt(x)+1;i>=1;i--)
		{
			if(x%i==0&&y%i==0)
			return i;
		}
	}
}
int main()
{
	ll x,y,ans1=0;
     scanf("%lld%lld",&n,&q);
     while(q--)
     {
     	scanf("%lld %lld",&x,&y);
     	if(x<y)
     	ans1=gcd(x,y);
     	else
     	ans1=gcd(y,x);
     	ll ans2=2;
     	printf("%lld\n",min(ans2,ans1));
	 }
	 return 0;
}