#include <bits/stdc++.h>
#include <chrono>
using namespace std;
using ll = long long;
const int BASE_LIMIT=36;
const ll MOD=1e8+9;
vector<vector<pair<int,int>>> fac;
void init(){
  fac.resize(2, vector<pair<int,int>>());
  for(int i=2;i<=BASE_LIMIT;++i){
    int p=2;
    vector<pair<int,int>> ps;
    int num=i;
    while(p*p<=num){
      int cnt=0;
      while(num%p==0){
        num/=p;
        cnt+=1;
      }
      if(cnt){
        ps.emplace_back(p,cnt);
      }
      p+=1;
    }
    if(num!=1) ps.emplace_back(num, 1);
    fac.emplace_back(ps);
  }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int Q;cin>>Q;
    for(int i=0;i<Q;++i){
      ll seeed, T;
      int N, K;
      cin>>seeed>>N>>K>>T;
      vector<ll> X(1,seeed);
      ll now=seeed;
      for(int j=0;j<N;++j){
        now=1+(now*(now+12345)%MOD);
        X.emplace_back(now);
      }

      int 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+=1;
          }
          cnts.emplace_back(c);
        }
        sort(cnts.begin(), cnts.end());
        int tans=accumulate(cnts.begin(),cnts.begin()+K,0)/cnt;
        ans=min(ans,tans);
      }
      cout<<ans<<'\n';
    }
    return 0;
}