#include"dzilib.h"
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define int long long
mt19937_64 rnd(20070819);

namespace PR{

int TEST_P[12]={2,3,5,7,11,13,17,19,23,29,31,37};

int mul(int x,int y,int p){
	__int128 a=x,b=y,c=p;
	return (int)(a*b%p);
}

int ksm(int x,int y,int p){
	int ans=1;
	for(int i=y;i;i>>=1,x=mul(x,x,p))if(i&1)ans=mul(ans,x,p);
	return ans;
}

bool chk(int a,int n){
	if(a>=n)return 1;
	int w=n-1,t=0;while(w%2==0)w/=2,t++;
	int x=ksm(a,w,n);
	for(int i=1;i<=t;i++){
		int y=mul(x,x,n);
		if(y==1&&x!=1&&x!=n-1)return 0;
		x=y;
	}
	if(x!=1)return 0;
	return 1;
}

bool is_prime(int n){
	for(int i=0;i<12;i++)if(!chk(TEST_P[i],n))return 0;
	return 1;
}

map<int,int>mp;

int randint(int l,int r){
	return rnd()%(r-l+1)+l;
}

int gcd(int x,int y){return y?gcd(y,x%y):x;}

int f(int x,int c,int p){
	__int128 xx=x,cc=c,pp=p;
	return (int)((xx*xx+cc)%pp);
}

int get(int n){
	// cout<<"get n = "<<n<<endl;
	if(n<=10000){
		for(int i=2;i*i<=n;i++)if(n%i==0)return i;
	}
	while(1){
		int x=randint(0,n-1),c=randint(0,n-1),p=f(x,c,n),q=f(f(x,c,n),c,n);
		if(p==q)continue;
		do{
			int t=1;
			for(int i=1;i<=128;i++){
				p=f(p,c,n),q=f(f(q,c,n),c,n);
				if(p==q||(p-q+n)%n==0)break;
				t=mul(t,(p-q+n)%n,n);
			}
			int d=gcd(n,t);
			if(d>1&&d!=n)return d;
		}while(p!=q);
	}
}

void solve(int n){
	// cout<<"solve n = "<<n<<endl;
	if(n==1)return ;
	if(is_prime(n)){mp[n]++;return ;}
	int x=get(n);
	solve(x),solve(n/x);
}

}

using PR::mp;

int P[10000000],pc=0;
bool chk_divs(int n,int d){
	if(__builtin_ctzll(n)<=12)return true;
	ll ans=1;
	for(int i=1;P[i]*P[i]<=n&&i<=pc;i++){
		int c=0;
		while(n%P[i]==0)n/=P[i],c++;
		ans*=(c+1);
		if(d%ans!=0)return false;
	}
	if(n>1)ans<<=1;
	return (ans==d);
	// mp.clear(),PR::solve(n);
	// ll ans=1;
	// cout<<"calc divs n = "<<n<<endl;
	// for(auto [x,y]:mp)ans*=(y+1);
	// return ans;
}

map<ll,ll>Map;
ll D=0,N;
ll qry(ll x){
	// cout<<"qry x = "<<1000+x<<endl;
	if(Map.find(x)!=Map.end())return Map[x];
	return Map[x]=Ask(x+D);
}

ll dfs(int k,ll now){ // x mod 2^k == now
	// if((1ll<<k)>N+D)return now;
	if((1ll<<(k+20))>N+D){
		int M=(1ll<<k);
		auto chk=[&](int x){
			// cout<<"try x = "<<x<<endl;
			for(auto [A,B]:Map)if(!chk_divs(x+A,B))return false;
			return true;
		};
		for(int x=now;x<=N+D;x+=M)if(chk(x))return x;
		return -1;
	}
	
	// cout<<"dfs k,now = "<<k<<" "<<now<<endl;
	// if(k==2&&now!=0)return -1;

	ll ad=(1ll<<k)-now;ad%=(1ll<<k);
	// cout<<"ad = "<<ad<<endl;
	for(int y=0;y<=3;y++){
		ll yy=(1ll<<k)*y;
		ll W=qry(ad+yy);
		// cout<<"y = "<<y<<" yy = "<<yy<<" W = "<<W<<endl;
		if(W%(k+2)==0){
			ll M=(1ll<<(k+2));
			ll xx=(1ll<<(k+1));
			xx=xx-ad-yy;
			xx=(xx%M+M)%M;
			ll ret=dfs(k+2,xx);
			if(ret!=-1)return ret;
		}
	}
	return -1;
}

ll C;
void solve(){
	Map.clear();
	D=0;
	// D=rnd()%(N/10);
	// cout<<"C = "<<C<<" D = "<<D<<endl;
	ll ret=dfs(0,0);
	Answer(ret-D);
}

bitset<100000001>vis;
signed main(){
	int tt=GetT(),Q=GetQ();
	C=GetC(),N=GetN();
	
	int V=1e8;
	int cnt=0;
	for(int i=2;i<=V;i++){
		if(!vis[i]){
			P[++pc]=i;
			for(int j=i+i;j<=V;j+=i)vis[j]=true;
		}
	}
	// cout<<"pc = "<<pc<<endl;
	// cout<<"T,Q,N,C = "<<tt<<" "<<Q<<" "<<N<<" "<<C<<endl;
	while(tt--)solve();
	return 0;
}