#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int gcd(int x,int y){
	if(x%y==0){
		return min(x,y);
	}
	else{
		gcd(y,x%y);
	}
}

int n,k;
int a,b;

int main(){
	scanf("%d %d",&n,&k);
	while(k--){
		scanf("%d %d",&a,&b);
		if(gcd(a,b)==1)
		printf("1");
		else
		printf("2");
		if(k)printf("\n");
	}
}