#include"dzilib.h"
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,C,q;
unordered_map<int,int>mp;

mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());
int ask(int x){
	if(mp.count(x))return mp[x];
	return mp[x]=Ask(x);
}

inline int solve(int x,int k){
    if((1ll<<k)>C)return (1ll<<k)-x;
    int a=ask(x),b=ask(x+(1ll<<k));
    if(a%(k+1)==0){
        for(int i=k+1;i<60;i++)
			if(b%(i+1)==0){
	            int y=solve(x+(1ll<<k),i);
				if(y!=-1)return y;
				else break;
	        }
    }
    if(b%(k+1)==0){
        for(int i=k+1;i<60;i++)
			if(a%(i+1)==0){
	            int y=solve(x,i);
				if(y!=-1)return y;
				else break;
	        }
    }
    return -1;
}

void Solve(){
    int T=GetT();n=GetN(),C=GetC(),q=GetQ();
    while(T--){
    	mp.clear();
		if(q>=1300)Answer(solve(rnd()%5000ll+1,0));
		else Answer(solve(rnd()%10000000000000ll+1,0));
	}
	
}

signed main(){
    int T=GetT();n=GetN(),C=GetC(),q=GetQ();
    while(T--){
    	mp.clear();
		if(q>=1300)Answer(solve(rnd()%5000+1,0));
		else Answer(solve(rnd()%1000000000000+1,0));
	}
	
	return 0;
}