#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<list>
#include<math.h>
#include<vector>
#include<stack>
#include<string>
#include<set>
#include<map>
#include<numeric>
#include<stdio.h>
#include<functional>
#include<time.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e5 + 10;
const ull mode = 10092272478850909;
const int inf = 0x3f3f3f3f;
const double pi = 3.14159265358979323846264338327950;
template <class T> inline T min(T a, T b, T c) { return min(min(a, b), c); }
template <class T> inline T max(T a, T b, T c) { return max(max(a, b), c); }
template <class T> inline T min(T a, T b, T c, T d) { return min(min(a, b), min(c, d)); }
template <class T> inline T max(T a, T b, T c, T d) { return max(max(a, b), max(c, d)); }

int pool(int a,int b)
{
   int m,n,c;
   m=a;
   n=b;
   while(b!=0)
   { 
	   c=a%b;
	   a=b; 
	   b=c;
   }
   return a;
}

int main()
{
	int n,q;
	scanf("%d %d",&n,&q);
	for(int i=0;i<q;i++)
	{
		int a,b;
		scanf("%d %d",&a,&b);
		if(pool(a,b)==1)
			printf("1\n");
		else if(a==b) printf("%d\n",0);
		else printf("2\n");
	}


    
	return 0;
}