#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define N 100010

int n, q;
int u, v;

int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
}

int main() {
	scanf("%d %d", &n, &q);
	while(q--) {
		scanf("%d %d", &u, &v);
		printf("%d\n", min(2, gcd(u, v)));
	}
	return 0;
}