#include <cstdio>
#include <cassert>
#include <iostream>
#include <unordered_map>
using namespace std;
const int M = 100005;
#define int long long
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m;
unordered_map<int,unordered_map<int,int> >mp[M],h;
int gcd(int a,int b) {return !b?a:gcd(b,a%b);}
int exgcd(int a,int b,int &x,int &y)
{
	if(b==0) {x=1;y=0;return a;}
	int d=exgcd(b,a%b,y,x);
	y-=(a/b)*x;return d;
}
int inv(int a,int p)
{
	int x=0,y=0,d=exgcd(a,p,x,y);
	assert(d==1);
	return (x%p+p)%p;
}
signed main()
{
	n=read();m=read();mp[1][1][0]=2;
	for(int x=2;x<=m;x++) if(m%x==0)
	{
		int a=1,b=1;h.clear();
		for(int i=2;;i++,swap(a,b),(b+=a)%=x)
		{
			if(h[a].count(b)) break;h[a][b]=1;
			int d=gcd(a,x),c=b*inv(a/d,x/d)%(x/d);
			if(!mp[x][d].count(c)) mp[x][d][c]=i;
		}
	}
	while(n--)
	{
		int a=read(),b=read();
		if(!a) {puts("0");continue;}
		if(!b) {puts("1");continue;}
		int d=gcd(gcd(a,b),m),k=m/d;
		a/=d;b/=d;d=gcd(b,k);
		int c=(k-a)*inv(b/d,k/d)%(k/d);
		if(mp[k][d].count(c))
			printf("%lld\n",mp[k][d][c]);
		else puts("-1");
	}
}