#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#ifdef _MSC_VER
#include "_lib_msc.h"
#endif
#define ITER(c)             __typeof__((c).begin())
#define FOREACH(it, c)      for (ITER(c) it=(c).begin(); it != (c).end(); ++it)
#define REP(i, n)           for(int(i)=0;(i)<(n);++(i))

const int INF = 1<<29;
const int MOD = 100000009;

// 素因数分解
vector<pair<int,int> > pdecomp(unsigned int n){
    vector<pair<int,int> > res;
    unsigned int e = 0; while(n % 2 == 0){ n /= 2, e++; }
    if(e) res.push_back(make_pair(2,e));
    for(unsigned int p = 3; p*p <= n; p += 2){
        unsigned int e = 0; while(n % p == 0){ n /= p, e++; }
        if(e) res.push_back(make_pair(p,e));
    }
    if(n != 1) res.push_back(make_pair(n,1));
    return res;
}

int solve(ll s, int n, int k, int b){
    vector<int> x;
    x.push_back((int)s);
    REP(i,n){
        s = 1+(s*s+s*12345)%MOD;
        x.push_back((int)s);
    }
    vector<pair<int,int> > d = pdecomp(b);

    int minv = INF;
    FOREACH(it, d){
        const int p = it->first, e = it->second;
        vector<int> y;
        FOREACH(jt, x){
            int n = *jt, c = 0;
            while(n % p == 0){
                c++, n /= p;
            }
            y.push_back(c);
        }
        sort(y.begin(), y.end());
        int sum = 0;
        REP(j,k) sum += y[j];
        minv = min(minv, sum/e);
    }

    return minv;
}

int main(){
    int N,s,n,k,b;
    cin >> N;

    REP(i,N){
        cin >> s >> n >> k >> b;
        cout << solve(s,n,k,b) << endl;
    }

    return 0;
}