#include<bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define dbg(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf = (int)1e9;
const double INF = 1e12, EPS = 1e-9;

int main(){
	int q; cin >> q;
	while(q--){
		int s, n, k, b, ans = inf;
		vi v;
		cin >> s >> n >> k >> b;
		v.pb(s);
		rep(i, n){
			s = 1 + ((ll)s * s + s * 12345ll) % ((int)1e8 + 9);
			v.pb(s);
		}
		
		for(int i = 2; i <= b; i++) if(b % i == 0){
			
			int c = 0;
			vi cnt;
			for(; b % i == 0; b /= i) c++;
			
			rep(l, n + 1){
				int k = 0;
				for(int j = v[l]; j % i == 0; j /= i) k++;
				cnt.pb(k);
			}
			sort(all(cnt));
			int x = 0;
			rep(l, k) x += cnt[l];
			ans = min(ans, x / c);
		}
		cout << ans << endl;
	}
	return 0;
}