#include<iostream>
#include<vector>
#include<algorithm>
#include<list>
using namespace std;
#define LL long long
const LL mod = 100000009;
typedef pair<int, LL> P;
int main(void){
	LL X[20000];
	vector<vector<LL> >POW(40);
	vector<list<P> > fact(40);
	int work[40];//素因数分解の作業用配列
	//POW[i][K]=i^k<=MODを満たすi,kについてあらかじめ求めておく
	for (int i = 2; i < 37; i++){
		LL num = 1;
		POW.reserve(40);
		while (num < mod){
			POW[i].push_back(num);
			num *= i;
		}
		POW[i].push_back(num*i);
		work[i] = i;
	}
	//[2,36]について素因数分解
	for (int i = 2; i < 37; i++){
		if (work[i] != 1){
			int p = work[i];
			for (int j = p; j < 37; j+=p){
				P pf = make_pair(p, 0ll);
				while (work[j] % p == 0)pf.second++,work[j]/=p;
				fact[j].push_back(pf);
			}
		}
	}
	int Q;
	cin >> Q;
	while (Q--){
		int N, K, B;
		LL res = mod;
		cin >> X[0] >> N >> K >> B;
		N++;
		for (int i = 1; i < N; i++){
			X[i] = ((X[i - 1] * (X[i - 1] + 12345)) % mod)+1;
		}

		for (auto& pf : fact[B]){
			int cnt[40] = { 0 };
			int sum = 0;
			int k = K;
			for (int i = 0; i < N; i++){
				int H = (int)POW[pf.first].size() - 1;
				int L = 0;
				while (H - L > 1){
					int M = (H + L) / 2;
					if (X[i] % POW[pf.first][M])H = M;
					else L = M;
				}
				cnt[L]++;
			}
			for (int i = 0; i < 40; i++){
				sum += min(k, cnt[i])*i;
				k -= min(k, cnt[i]);
			}
			res = min(res, sum / pf.second);
		}
		/*
for (int i = 0; i < N; i++){
			int H = (int)POW[B].size() - 1;
			int L = 0;
			while (H - L > 1){
				int M = (H + L) / 2;
				if (X[i] % POW[B][M])H = M;
				else L = M;
			}
			X[i] = L;
			cout << " " << X[i] << endl;
		}
		*/

		cout << res << endl;
	}
	
}