#include<stdio.h>
int gcd(int x,int y){
	if(y==0) return x;
	gcd(y,x%y);
}
int main(){
	int n,k;
	int a,b;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=k;i++){
		scanf("%d%d",&a,&b);
		if(gcd(a,b)!=1) printf("2\n");
		else printf("1\n");
	}
}