#include <stdio.h>
#include <stdlib.h>
int *Order = 0;
int Order_n = 0;
int cmp(const void* a, const void* b)
{
  int rc;
  int i;
  for (i=0; i<Order_n; i++) {
    rc = ((int*)a)[Order[i]] - ((int*)b)[Order[i]];
    if (rc != 0) {
      break;
    }
  }
  return rc;
}
void factor(int N, int* pr, int *pow, int *nu)
{
  (*nu) = 0;
  int pw;
  for (pw=0; N%2==0; pw++) {
    N/=2;
  }
  if (pw != 0) {
    pr[*nu] = 2;
    pow[*nu] = pw;
    (*nu)++;
  }
  int i;
  for (i=3; i*i<=N; i+=2) {
    for (pw=0; N%i==0; pw++) {
      N/=i;
    }
    if (pw != 0) {
      pr[*nu] = i;
      pow[*nu] = pw;
      (*nu)++;
    }
  }
  if (N != 1) {
    pr[*nu] = N;
    pow[*nu] = 1;
    (*nu)++;
  }
  return;
}
void genX(int seed, int N, int *X)
{
  //100000009 = 149 * 671141;
  int mod = 100000009;
  long long int Y, Z;
  int i;
  X[0] = seed;
  for (i=1; i<=N; i++) {
    Y = X[i-1];
    Y = Y*Y;
    Z = X[i-1];
    Z = Z*12345;
    Y += Z;
    Y %= mod;
    X[i] = 1 + Y;
  }
  return;
}
int main()
{
  int Q;
  int *seed;
  int *N;
  int *K;
  int *B;
  scanf("%d", &Q);
  seed = (int*)malloc(sizeof(int)*Q);
  N = (int*)malloc(sizeof(int)*Q);
  K = (int*)malloc(sizeof(int)*Q);
  B = (int*)malloc(sizeof(int)*Q);
  int i;
  for (i=0; i<Q; i++) {
    scanf("%d", &(seed[i]));
    scanf("%d", &(N[i]));
    scanf("%d", &(K[i]));
    scanf("%d", &(B[i]));
  }

  int maxN = 0;
  for (i=0; i<Q; i++) if (maxN < N[i]) maxN = N[i];
  int *X = (int*)malloc(sizeof(int)*(maxN+1));

  int maxB = 0;
  for (i=0; i<Q; i++) if (maxB < B[i]) maxB = B[i];
  int pr_n;
  for (i=1,pr_n=0; i<maxB; i*=2,pr_n++) ;
  pr_n++;
  int *pr = (int*)malloc(sizeof(int)*pr_n);
  int *pow = (int*)malloc(sizeof(int)*pr_n);
  Order = (int*)malloc(sizeof(int)*pr_n);
  pr_n = 0;

  int total;
  int ans;
  int j;
  int k;
  int l;
  int permu2[2][2] = {{0,1},{1,0}};
  int permu3[6][3] = {{0,1,2},{0,2,1},{1,2,0},{1,0,2},{2,0,1},{2,1,0}};
  for (i=0; i<Q; i++) {
    factor(B[i], pr, pow, &pr_n);
    genX(seed[i], N[i], X);

    int **Xpow = (int**)malloc(sizeof(int*)*(N[i]+1));
    Xpow[0] = (int*)malloc(sizeof(int)*(N[i]+1)*pr_n);
    for (j=1; j<=N[i]; j++) Xpow[j] = &(Xpow[j-1][pr_n]);

    for (j=0; j<=N[i]; j++) {
      for (k=0; k<pr_n; k++) {
        for (Xpow[j][k] = 0; X[j]%pr[k]==0; Xpow[j][k]++) {
          X[j]/=pr[k];
        }
      }
    }

    switch (pr_n) {
    case 1:
      Order_n = pr_n;
      Order[0] = 0;
      qsort(Xpow[0], N[i]+1, sizeof(int)*pr_n, cmp);
      for (k=0; k<pr_n; k++) {
        total = 0;
        for (j=0; j<K[i]; j++) {
          total += Xpow[j][k];
        }
        ans = total/pow[k];
      }
      break;
    case 2:
      ans = ~(1 << 31);
      Order_n = pr_n;
      for (l=0; l<2; l++) {
        Order[0] = permu2[l][0];
        Order[1] = permu2[l][1];
        qsort(Xpow[0], N[i]+1, sizeof(int)*pr_n, cmp);
        for (k=0; k<pr_n; k++) {
          total = 0;
          for (j=0; j<K[i]; j++) {
            total += Xpow[j][k];
          }
          if (total/pow[k] < ans) ans = total/pow[k];
        }
      }
      break;
    case 3:
      ans = ~(1 << 31);
      Order_n = pr_n;
      for (l=0; l<6; l++) {
        Order[0] = permu3[l][0];
        Order[1] = permu3[l][1];
        Order[2] = permu3[l][2];
        qsort(Xpow[0], N[i]+1, sizeof(int)*pr_n, cmp);
        for (k=0; k<pr_n; k++) {
          total = 0;
          for (j=0; j<K[i]; j++) {
            total += Xpow[j][k];
          }
          if (total/pow[k] < ans) ans = total/pow[k];
        }
      }
      break;
    default:
      printf("!?\n");
      exit(1);
      break;
    }
    printf("%d\n", ans);

    free(Xpow[0]);
    free(Xpow); Xpow=0;
  }

  return 0;
}