#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int gcd(int a,int b)
{
	return b?gcd(b,a%b):a;
}
int t,n,q;
int x[maxn];
char s[105];
int main()
{
	scanf("%d%d",&n,&q);
	while(q--)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		if(gcd(u,v)==1)printf("1\n");
		else printf("2\n");
	}
}