#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#define clr(a,b) memset(a,b,sizeof(a))
#define ll long long

using namespace std;

const int maxn=1e5+10;
int n,q;
int x,y;

int gcd(int a,int b)
{
	return b?gcd(b,a%b):a;
}
		
int main()
{
	scanf("%d %d",&n,&q);
	while(q--)
	{
		scanf("%d %d",&x,&y);
		int minn=min(min(gcd(x,y),gcd(x-1,y)+1),gcd(x,y-1)+1);
		printf("%d\n",minn);
	}
}