#include <cstdio>
#include <cstring>
#include <string>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>　
#include <iostream>
#include <cmath>
//#include <process.h>
using namespace std;
const int inf = 0x3f3f3f3f;
#define ll long long
#define pii 3.1415926897932384626
int i, j, k;
int n, m;
int a[100010];
int gcd(int a, int b) {
	if (b == 0) return a;  return gcd(b, a % b);
}
int main() {

	scanf("%d %d",&n,&m);
	while(m--){
		int x, y;
		int ans;
		scanf("%d%d", &x, &y);
		if(gcd(x,y)==1)
			ans=1;
		else
			ans=2;
		printf("%d\n", ans);
	
	}
	/*scanf("%d %d",&n,&m);
	for(i=0;i<n;i++)
		scanf("%lf",&a[i]);
	for(i=0;i<n;i++){
		int res;
		int s=m;
		double kk;
		double ans=a[i];
		while(s--){
			kk=sqrt(ans);
			res=(int)(kk+0.99);
			res*=10;
			ans=(double)res;
		}
	    printf("%.0f",ans);
		if(i!=n-1)
		    printf(" ");
		else
			printf("\n");
	}*/
//	system("pause");
	return 0;
}