#include<bits/stdc++.h>
#define maxn 100010

using namespace std;

inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

int n,m; 

int a,b;

int dp[maxn];

map<int,int>s;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	n=read(),*=read();
	for(int i=1;i<=n;i++){
		memset(dp,0,sizeof(dp));
		s.clear();
		a=read(),b=read();
		if(a==0){
			cout<<0<<"\n";
			continue;
		}
		if(b==0){
			cout<<1<<"\n";
			continue;
		}
		dp[0]=a,dp[1]=b;
		for(int j=2;j<=100000;j++){
			dp[j]=(dp[j-1]+dp[j-2])%m,cout<<dp[j]<<"\n";
			if(dp[j]==0){
				cout<<j<<"\n";
				break;
			}
			s[dp[j]]++;
			if(s[dp[j]]==2){
				cout<<-1<<"\n";
				break;
			}
		}
	}
	return 0;
}