#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>

using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD 1000000007
#define P pair<ll, ll>

ll Q, mod = (ll)1e8 + 9;
int main() {
	cin >> Q;
	REP(qq, Q) {
		ll n, k, b, ans = INF;
		vector<ll> s(1);
		vector<P> list;
		cin >> s[0] >> n >> k >> b;
		ll bb = b;
		REP(i, n) s.push_back(1 + (((s[i] * s[i] % mod) + s[i] * 12345) % mod));
		for (int i = 2; i <= b; i++)
		{
			if (bb % i == 0) {
				ll now = 0;
				while (bb % i == 0) {
					now++;
					bb /= i;
				}
				list.push_back(P(i, now));
			}
		}
		REP(i, list.size()) {
			priority_queue<ll> q;
			ll now = 0;
			REP(j, s.size()) {
				ll nownow = 0;
				if (s[j] == 0) {
					ans = min(ans, 1ll);
					nownow = 1;
				}
				else {
					while (s[j] % list[i].first == 0) {
						nownow++;
						s[j] /= list[i].first;
					}
				}
				now += nownow;
				q.push(nownow);
				if (q.size() > k) {
					now -= q.top();
					q.pop();
				}
			}
			ans = min(ans, now / list[i].second);
		}
		cout << ans << endl;
	}
}