/*
 * IPSC 1999
 * Problem Rain
 * author solution
 * reads input from g.txt
 */

#include <stdio.h>
FILE *f;

long si,ti,sj,tj; // static only because of speed

inline int Meteoronome1()
{
  si = (78901 + 31* (si)) % 699037;
  ti = (23456 + 64* (ti)) % 2097151;
  return (si % 100+ 1) * (ti % 100 + 1);
}


inline int Meteoronome2()
{
  sj = (78901 + 31* (sj)) % 699037;
  tj = (23456 + 64* (tj)) % 2097151;
  return (sj % 100+ 1) * (tj % 100 + 1);
}

long compute(long s0, long t0, long N, long M)
{
  long sum;
  long i, j, min, minj, tmp, sumj;

  si = sj = s0;
  ti = tj = t0;
  sum = 0;
  min = N + 1;
  minj = -1;
  i = 0; j = 0;


  while (j<N) {

    while (sum <= M && j < N) {
      sum += Meteoronome2();
      j++;
    }
    while (sum>M) {
      sum -= Meteoronome1();
      i++;
    }
    if (j - i < min) {
      minj = j; min = j - i;
    }
  }
  minj = minj;
  return min;
}

int main(void)
{
  long int s0,t0, N,M, K, L;
  int i;

  f = fopen("g.txt","r");
  fscanf(f,"%ld ",&L);

  for(i = 0; i < L; i++) {
    fscanf (f, "%ld %ld %ld %ld ", &s0, &t0, &N, &M);
    K = compute (s0, t0, N, M);
    printf ("%ld\n", K);
  }

  fclose(f);
  return 0;
}