#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<map>
#include<stack>
#include<math.h>;
#include<queue>
using namespace std;
int gcd(int a,int b) {
	return b==0?a:gcd(b,a%b);
}
int main() {
	int n,q;
	scanf("%d %d",&n,&q);
	while(q--) {
		int a1,b1;
		scanf("%d %d",&a1,&b1);
		printf("%d\n",min(2,gcd(a1,b1)));
	}
}