#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=100010;
const int inf =0x3f3f3f3f;
int n,m,k,t;
int x,y;
int a[maxn];
char ch[maxn];
int gcd(int a,int b)
{
	return b? gcd(b,a%b):a;
}
int main()
{
	scanf("%d %d",&n,&k);
	while(k--)
	{
		scanf("%d %d",&x,&y);
		printf("%d\n",min(2,gcd(x,y)));
	}
}