#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>

using namespace std;
int main(){
  int Q;
  scanf("%d",&Q);
  int primes[]={2,3,5,7,11,13,17,19,23,29,31};
  int n_prime=11;
  for( int qi = 0 ; qi < Q; qi++ ){
    int seed,N,K,B;
    scanf("%d%d%d%d",&seed,&N,&K,&B);
    int ps[3];
    int pcnt[3];
    int psize=0;
    for( int pi = 0 ; pi < n_prime; pi++ ){
      int p = primes[pi];
      int cnt =0;
      while(B%p==0){
        cnt++;
        B/=p;
      }
      if(cnt>0){
        //cout << p << ", "<< cnt;
        ps[psize]=p;
        pcnt[psize]=cnt;
        psize++;
      }
    }
    priority_queue<int> pq[psize];
    for( int i = 0 ; i < N+1; i++ ){
      long long x = seed;
      //cout << seed;
      for( int j = 0 ; j < psize; j++ ){
        int p = ps[j];
        int cnt = 0;
        while( seed%p == 0 ){
          cnt++;
          seed/=p;
        }
        //cout <<" "<<cnt;
        if( pq[j].size() < K ){
          pq[j].push(cnt);
        }
        else if( pq[j].top() > cnt ){
          pq[j].pop();
          pq[j].push(cnt);
        }
      }
      //cout << endl;
      long long s= x*x;
      s%=100000009;
      s += x*12345;
      s%=100000009;
      seed=s+1;
    }
    int ans = INT_MAX;
    for( int pi = 0 ; pi < psize; pi++ ){
      int div = pcnt[pi];
      int sum = 0;
      for( int j = 0 ; j < K ; j++ ){
        sum += pq[pi].top();
        pq[pi].pop();
      }
      //cout << sum << "/ "<< div<<endl;
      ans = min(ans,sum/div);
    }
    printf("%d\n",ans);
  }
  return 0;
}