#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
ll gcd(ll x,ll y)
{
	if(!y) return x;
	return gcd(y,x%y);
}
ll lcm(ll x,ll y)
{
	return x/gcd(x,y)*y;
}
void exgcd(ll a,ll b,ll &x,ll &y)
{
	if(!b)
	{
		x=1,y=0;
		return;
	}
	exgcd(b,a%b,y,x);
	y-=(a/b)*x;
}
ll getinv(ll x,ll mod)
{
	ll ans1,ans2;
	exgcd(x,mod,ans1,ans2);
	return (ans1%mod+mod)%mod;
}
struct pt
{
	ll x,l;
	pt(ll x=0,ll l=0):x(x),l(l){} 
};
pt operator*(pt a,pt b)
{
	if(a.x==-1||b.x==-1) return pt(-1,-1);
	ll ans1,ans2,g=gcd(a.l,b.l),mod;
	mod=a.l/g;
	if((a.x-b.x)%g!=0) return pt(-1,-1); 
	exgcd(a.l,b.l,ans2,ans1);
	ans1=ans1*((a.x-b.x)/g)%mod;
	ans1=(ans1%mod+mod)%mod;
	return pt(ans1*b.l+b.x,lcm(a.l,b.l));
}
int n,m,a[105][2],b[105],at,c[105],ct,rc[200005],f[105][100005],vis[200005];
void solve(int x)
{
	for(int i=2;i<=x;i++)
		if(x%i==0)
		{
			a[++at][0]=i;
			a[at][1]=1;
			b[at]=0;
			while(x%i==0)
			{
				b[at]++;
				a[at][1]*=i;
				c[++ct]=a[at][1];
				x/=i;
			}
		}
	if(x!=1)
	{
		a[++at][0]=x;
		a[at][1]=x;
		b[at]=1;
		c[++ct]=x;
	}
}
int dfs(int u,int x)
{
	if(f[x][u]!=-2) return f[x][u];
	if(vis[u]==1) return f[x][u]=-1;
	vis[u]=1;
	int g=gcd(u,c[x]);
	if(g!=1)
	{
		int v=(1+u)%c[x];
		int w=1ll*(u+v)*getinv(v,c[x])%c[x];
		int q=dfs(w,x);
		vis[u]=0;
		if(q==-1) return f[x][u]=-1;
		f[x][u]=q+2;
		return f[x][u];
	}
	int v=1ll*(1+u)*getinv(u,c[x])%c[x];
	int q=dfs(v,x);
	vis[u]=0;
	if(q==-1) return f[x][u]=-1;
	f[x][u]=q+1;
	return f[x][u];
}
void getans(int x)
{
	for(int i=0;i<c[x];i++)
		f[x][i]=-2,vis[i]=0;
	f[x][0]=1;
	for(int i=1;i<c[x];i++)
		dfs(i,x);
/*	printf("getans:x=%d,c=%d\n",x,c[x]);
	for(int i=0;i<c[x];i++)
		printf("%d ",f[x][i]);
	printf("\n");*/
}
pt solve3(int x,int y,int z)
{
	if(!x) return pt(0,f[z][1]+1);
	if(!y) return pt(1,f[z][1]+1);
	int g=gcd(x,c[z]),fl=0;
	if(g!=1)
	{
		int tmp=(x+y)%c[z];
		x=y;
		y=tmp;
		fl=1;
	}
	y=1ll*y*getinv(x,c[z])%c[z];
	if(f[z][y]==-1) return pt(-1,-1);
	return pt(f[z][y]+fl,f[z][1]+1);
}
pt solve2(int x,int y,int z)
{
	x%=a[z][1],y%=a[z][1];
//	printf("solve2:x=%d,y=%d,z=%d\n",x,y,z);
	if(x==0&&y==0) return pt(0,1);
	int g=gcd(gcd(x,y),a[z][1]);
	return solve3(x/g,y/g,rc[a[z][1]/g]);
}
int main()
{
	scanf("%d%d",&n,&m);
	solve(m);
	/*for(int i=1;i<=ct;i++)
		fprintf(stderr,"%d ",c[i]);
	fprintf(stderr,"\n");*/
	for(int i=1;i<=ct;i++)
		rc[c[i]]=i;
//	printf("---\n");
	for(int i=1;i<=ct;i++)
		getans(i);
	for(int i=1;i<=n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		pt ans;
		ans=pt(0,1);
		for(int j=1;j<=at;j++)
		{
			ans=ans*solve2(x,y,j);
	//		printf("x=%d,y=%d,j=%d,solve2=%lld,%lld\n",x,y,j,solve2(x,y,j).x,solve2(x,y,j).l);
		}
		printf("%lld\n",ans.x);
	}
	return 0;
}