#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int Q;
vector<pair<int,int> >fact(int B)
{
	vector<pair<int,int> >ret;
	for(int i=2;i*i<=B;i++)if(B%i==0)
	{
		int c=0;
		while(B%i==0)B/=i,c++;
		ret.push_back(make_pair(i,c));
	}
	if(B>1)ret.push_back(make_pair(B,1));
	return ret;
}
main()
{
	cin>>Q;
	for(;Q--;)
	{
		long x;
		int N,K,B;
		cin>>x>>N>>K>>B;
		vector<pair<int,int> >ps=fact(B);
		vector<vector<int> >A(N+1);
		for(int i=0;i<=N;i++)
		{
			{
				vector<int>now(ps.size());
				long t=x;
				for(int j=0;j<ps.size();j++)
				{
					int p=ps[j].first;
					int c=0;
					while(t%p==0)t/=p,c++;
					now[j]=c;
				}
				A[i]=now;
			}
			x=1+(x*x+x*12345)%100000009;
		}
		int ans=1e9;
		for(int i=0;i<ps.size();i++)
		{
			sort(A.begin(),A.end(),[&i](const vector<int>&a,const vector<int>&b){
				return a[i]<b[i];
			});
			vector<int>cnt(ps.size());
			for(int j=0;j<K;j++)
			{
				for(int k=0;k<ps.size();k++)cnt[k]+=A[j][k];
			}
			int now=1e9;
			for(int j=0;j<ps.size();j++)now=min(now,cnt[j]/ps[j].second);
			ans=min(ans,now);
		}
		cout<<ans<<endl;
	}
}