/* -*- coding: utf-8 -*-
 *
 * 28.cc: No.28 末尾最適化 - yukicoder
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 10000;
const int INF = 1 << 30;

const int PN = 4;
const int pnums[PN] = {2, 3, 5, 7};

typedef long long ll;
const ll MOD = 100000009;

/* typedef */

typedef vector<int> vi;
typedef pair<int,int> pii;

/* global variables */

ll xs[MAX_N + 1];
int xps[PN][MAX_N + 1];
pii xpis[MAX_N + 1];

/* subroutines */

void print_pd(vi &ps, vi &es) {
  for (int i = 0; i < ps.size(); i++) {
    if (i) putchar('+');
    printf("%d^%d", ps[i], es[i]);
  }
  putchar('\n');
}

bool prime_decomp(int n, vi &ps, vi &es) {
  ps.clear();
  es.clear();

  for (int i = 0; i < PN; i++) {
    int pi = pnums[i];
    if (pi * pi > n) {
      if (n > 1) ps.push_back(n), es.push_back(1);
      return true;
    }

    if (n % pi == 0) {
      int fi = 0;
      while (n % pi == 0) n /= pi, fi++;
      ps.push_back(pi);
      es.push_back(fi);
    }
  }
  return false;
}

/* main */

int main() {
  int qn;
  cin >> qn;
  while (qn--) {
    int n, k, b;
    cin >> xs[0] >> n >> k >> b;

    for (int i = 1; i <= n; i++) {
      ll x0 = xs[i - 1] % MOD;
      xs[i] = ((x0 * x0) % MOD + (x0 * 12345) % MOD) % MOD + 1;
    }
    
    vi bps, bes;
    prime_decomp(b, bps, bes);
    int pn = bps.size();
    //print_pd(bps, bes);

    for (int i = 0; i < pn ;i++) {
      int &pi = bps[i];
      for (int j = 0; j <= n; j++) {
	int cnt = 0;
	while (xs[j] % pi == 0) cnt++, xs[j] /= pi;
	xps[i][j] = cnt;
      }
    }
      
    int minz = INF;
    for (int i = 0; i < pn ;i++) {
      for (int j = 0; j <= n; j++)
	xpis[j].first = xps[i][j], xpis[j].second = j;
      sort(xpis, xpis + n + 1);

      int z = 0;
      for (int j = 0; j < k; j++) z += xps[i][xpis[j].second];
      z /= bes[i];

      if (minz > z) minz = z;
    }

    printf("%d\n", minz);
  }
  return 0;
}