#include <bits/stdc++.h>
const long long int infL = 1LL << 60;
int solve(long long int start, long long int end, long long int p,
          long long int q) {
  long long int interval = 1;
  while (interval * interval < end - start) interval++;
  std::vector<std::pair<long long int, long long int>> remainders,
      remainders_copy;
  for (long long int i = start; i < start + interval; i++) {
    long long int key = 2 * p * i % (2 * q);
    remainders.push_back({key, i});
  }
  std::sort(remainders.begin(), remainders.end());
  remainders_copy = remainders;
  remainders.clear();
  remainders.push_back(remainders_copy[0]);
  for (int i = 1; i < remainders_copy.size(); i++) {
    if (remainders_copy[i].first != remainders_copy[i - 1].first)
      remainders.push_back(remainders_copy[i]);
  }
  remainders_copy.clear();
  long long int answervalue = -1, answerdistance = infL, iteration = 0;
  for (iteration = 0; start + (iteration + 1) * interval <= end; iteration++) {
    long long int look = q - iteration * interval * 2 * p;
    look %= (2 * q);
    if (look < 0) look += 2 * q;
    long long int baseindex =
        std::lower_bound(remainders.begin(), remainders.end(),
                         std::make_pair(look, -infL)) -
        remainders.begin();
    for (int j = 0; j >= -1; j--) {
      long long int thisindex = (baseindex + j) % remainders.size();
      if (thisindex < 0) thisindex += remainders.size();
      long long int thisvalue =
          remainders[thisindex].second + iteration * interval;
      long long int thisdistance = look - remainders[thisindex].first;
      if (thisdistance < 0) thisdistance *= -1;
      if (thisdistance > q) thisdistance = 2 * q - thisdistance;
      if (std::make_pair(thisdistance, thisvalue) <
          std::make_pair(answerdistance, answervalue)) {
        answervalue = thisvalue;
        answerdistance = thisdistance;
      }
    }
  }
  for (long long int v = start + iteration * interval; v < end; v++) {
    long long int thisdistance = (2 * p * v) % (2 * q) - q;
    if (thisdistance < 0) thisdistance *= -1;
    if (std::make_pair(thisdistance, v) <
        std::make_pair(answerdistance, answervalue)) {
      answerdistance = thisdistance;
      answervalue = v;
    }
  }
  return answervalue;
}
int main(void) {
  int testcases;
  scanf("%d", &testcases);
  for (int t = 0; t < testcases; t++) {
    long long int a, b, p, q;
    scanf("%lld %lld %lld %lld", &a, &b, &p, &q);
    printf("%d\n", solve(a, b + 1, p, q));
  }
  return 0;
}
