#include<iostream>
#include<stdio.h>
#include<string>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
int gcd(int m,int n){
	int t=m%n;
	while(t!=0){
		m=n;
		n=t;
		t=m%n;
	}
	return n;
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	while(m--){
		int ans;
		int p,q;
		scanf("%d%d",&p,&q);
		if(gcd(p,q)==1)
			ans=1;
		else
			ans=2;
		printf("%d\n",ans);
	}
	return 0;
}