#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
constexpr ll MOD=1e8+9;
vector<vector<pair<int,int>>> fac;
void init(){
    fac.resize(37,vector<pair<int,int>>());
    for(int i=2;i<=36;++i){
        int p=2;
        vector<pair<int,int>> ps;
        auto num=i;
        while(p*p<=num){
            int cnt=0;
            while(num%p==0){
                ++cnt;
                num/=p;
            }
            if(cnt)ps.emplace_back(p,cnt);
            p+=1;
        }
        if(num!=1)ps.emplace_back(num,1);
        fac[i]=ps;
    }
}
void solve(){
    ll seed,T;
    ll N,K;
    cin>>seed>>N>>K>>T;
    vector<ll> X(1,seed);
    ll now=seed;
    for(int j=0;j<N;++j){
        now=1+(now*(now+12345)%MOD);
        X.emplace_back(now);
    }

    ll ans=MOD;
    for(auto&[p,cnt]:fac[T]){
        vector<int> cnts;
        for(const auto&x:X){
            auto num=x;
            int c=0;
            while(num%p==0){
                num/=p;
                ++c;
            }
            cnts.emplace_back(c);
        }
        ranges::sort(cnts);
        ll tans=accumulate(begin(cnts),begin(cnts)+K,0LL)/cnt;
        ans=min(ans,tans);
    }
    cout<<ans<<'\n';
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    init();
    int T=1; cin>>T;
    while(T--)solve();
    return 0;
}