#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <numeric>
#include <cctype>
#include <tuple>
#include <climits>
#include <bitset>
#include <cassert>
#include <random>

#ifdef _MSC_VER
#include <agents.h>
#endif

#define FOR(i, a, b) for(int i = (a); i < (int)(b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define REV(v) v.rbegin(), v.rend()
#define MEMSET(v, s) memset(v, s, sizeof(v))
#define UNIQUE(v) (v).erase(unique(ALL(v)), (v).end())
#define MP make_pair
#define MT make_tuple

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

template<class T> inline void chmax(T& a, const T& b) { if (b > a) a = b; }
template<class T> inline void chmin(T& a, const T& b) { if (b < a) a = b; }

const double EPS = 1e-9;

vector<P> fact[40];

void factorize(int x){
	int xx = x;
	for (int i = 2; i*i <= xx; ++i){
		int cnt = 0;
		while (xx%i == 0)++cnt, xx /= i;
		if (cnt) fact[x].push_back(MP(i, cnt));
	}
	if (xx != 1) fact[x].push_back(MP(xx, 1));
}

const ll mod = 100000009;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);

	for (int i = 2; i <= 36; ++i) factorize(i);

	int q;
	cin >> q;
	while (q--){
		ll seed, n, k, b;
		cin >> seed >> n >> k >> b;
		vector<int> v[40];
		++n;
		rep(i, n){
			ll x = 1 + (seed*seed + seed * 12345) % mod;
			swap(x, seed);
			for (auto p : fact[b]){
				int cnt = 0;
				while (x % p.first == 0) x /= p.first, ++cnt;
				v[p.first].push_back(cnt);
			}
		}
		int ans = 1e9;
		for (auto p : fact[b]){
			auto &vv = v[p.first];
			sort(ALL(vv));
			int cnt = 0;
			rep(i, k) cnt += vv[i];
			ans = min(ans, cnt / p.second);
		}
		cout << ans << '\n';
	}

	return 0;
}