#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<math.h>
#include<string.h>
#include<cstring>
using namespace std;
inline int Gcd(int n,int m)
{
	int r;
	if(n < m)
	{
		r = n;
		n = m;
		m = r;
	}
	while(n % m != 0)
	{
		r = n % m;
		n = m;
		m = r;
	}
	return m;
}
//int c[100010];
int main(void)
{

	//printf("TFT\n");
	/*int t,ans;
	scanf("%d",&t);
	while(t--)
	{
		ans = 0;
		char c[110];
		scanf("%s",c);
		int len = strlen(c),i;
		for(i = 0;i < len;i++)
		{
			if(c[i] == 'a' || c[i] == 'e' || c[i] == 'i' || c[i] == 'o' || c[i] == 'u')
			{
				ans++;
			}
		}
		printf("%d\n",ans);
	}*/
	/*printf("                                                            \n");
	printf("                                                            \n");
	printf("                                                            \n");
	printf("                *********           *********               \n");
	printf("            *****************   *****************           \n");
	printf("          ****************************************          \n");
	printf("         *******************************************        \n");
	printf("        *********************************************       \n");
	printf("        *********************************************       \n");
	printf("        *********************************************       \n");
	printf("        *********************************************       \n");
	printf("        *********************************************       \n");
	printf("        *********************************************       \n");
	printf("         *******************************************        \n");
	printf("          *****************************************         \n");
	printf("          ****************************************          \n");
	printf("            *************************************           \n");
	printf("             ***********************************            \n");
	printf("              *********************************             \n");
	printf("                *****************************               \n");
	printf("                  *************************                 \n");
	printf("                    *********************                   \n");
	printf("                       ***************                      \n");
	printf("                          *********                         \n");
	printf("                             ***                            \n");
	printf("                                                            \n");
	printf("                                                            \n");
	printf("                                                            \n");
	printf("                                                            \n");
	printf("                                                            \n");*/

	/*int n,k,i;
	while(~scanf("%d %d",&n,&k))
	{
		for(i = 0;i < n;i++)
		{
			scanf("%d",c + i);
		}
		if(k >= 100)
		{
			for(i = 0;i < n;i++)
			{
				printf("10");
				if(i != n - 1)
				{
					printf(" ");
				}
			}
			printf("\n");
		}
		else
		{
			for(i = 0;i < n;i++)
			{
				for(int j = 0;j < k;j++)
				{
					c[i] = (int)ceil(sqrt(c[i] * 1.0));
				}
				printf("%d",c[i] * 10);
				if(i != n - 1)
				{
					printf(" ");
				}
			}
			printf("\n");
		}
	}*/

	/*int t,n,i,j;
	int c[1010],ans[1010];
	memset(c,0,sizeof(c));
	for(i = 2;i <= 1000;i++)
	{
		if(c[i] == 0)
		{
			for(j = i + i;j <= 1000;j += i)
			{
				c[j] = 1;
			}
		}
	}
	ans[1] = 0;
	for(i = 2;i <= 1000;i++)
	{
		ans[i] = ans[i - 1] + 1 - c[i];
	}
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		printf("%d\n",ans[n] - ans[1]);
	}*/

	int n,q,i,j;
	while(~scanf("%d %d",&n,&q))
	{

		while(q--)
		{
			scanf("%d %d",&i,&j);
			if(i == j)
			{
				printf("0\n");
			}
			else if(Gcd(i,j) != 1)
			{
				printf("2\n");
			}
			else
			{
				printf("1\n");
			}
		}
	}
	return 0;
}