#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RANGE(vec) (vec).begin(),(vec).end()

using namespace std;

std::map<int,int> primeFactorize(int n) {
        std::map<int,int> res;
        for (int i = 2; i*i <= n; ++i)
        {
            while (n%i==0)
            {
                ++res[i];
                n /= i;
            }
        }
        if (n!= 1)
            res[n] = 1;
        return std::move(res);
}

class TailCallOptim {
public:
    void solve(void) {
            int Q;
            cin>>Q;

            REP(_,Q)
            {
                int seed, n,K,B;
                cin>>seed>>n>>K>>B;
                vector<ll> x(n+1);
                x[0] = seed;
                FOR(i,1,n+1)
                    x[i] = 1+(x[i-1]*x[i-1] + x[i-1]*12345 + 100000009) % 100000009;
                //
                // B を素因数分解する
                // B = P1^K1 * ... Pm^Km とする
                //
                // 一方 T = P1^L1 * ... Pm^Lm * S とすると
                //
                // T の B 進表現末尾 0 の個数は min { Li/Ki } となる
                //                              i
                // こいつを最小化すればよい
                int ans = (1<<30);
                auto primes = primeFactorize(B);
                // 各素数ごとに調べる
                for (auto pk : primes)
                {
                    int p,k;
                    tie(p,k) = pk;

                    vector<int> ks(n+1,0);
                    // 各 x の p^k の冪を求める
                    REP(i,n+1)
                    {
                        int l = 0;
                        ll  tmp = x[i];
                        while (tmp % p == 0)
                        {
                            ++l;
                            tmp /= p;
                        }
                        ks[i] = l;
                    }
                    sort(RANGE(ks));
                    int L = 0;
                    // L が小さくなるように ks を小さいものから K 個加算
                    REP(i,K)
                        L += ks[i];
                    ans = min(ans, L/k);// 最小値を更新
                }
                cout<<ans<<endl;
            }
    }
};

#if 1
int main(int argc, char *argv[])
{
        ios::sync_with_stdio(false);
        auto obj = new TailCallOptim();
        obj->solve();
        delete obj;
        return 0;
}
#endif