#include <bits/stdc++.h>
using namespace std;
long long a, b, p, q;
void input() { cin >> a >> b >> p >> q; }
long long gcd(long long x, long long y) {
  while (y) {
    long long z = x % y;
    x = y;
    y = z;
  }
  return x;
}
long long inverse(long long p, long long q) {
  long long _q = q;
  long long x = 1;
  long long y = 0;
  long long _x = 0;
  long long _y = 1;
  while (q) {
    long long m = p / q;
    long long d = p % q;
    long long tmp = x;
    x = _x;
    _x = tmp - m * _x;
    tmp = y;
    y = _y;
    _y = tmp - m * _y;
    p = q;
    q = d;
  }
  if (x < 0) x += _q;
  return x;
}
long long e;
long long get(long long target) {
  long long index = (target * e) % q;
  long long z = a / q * q;
  index += z;
  if (index < a) {
    index += q;
  }
  if (index > b) return -1;
  return index;
}
long long solve0() {
  long long min_d = numeric_limits<long long>::max();
  long long ans = 0;
  for (long long i = a; i <= b; ++i) {
    long long index = (i * p) % q;
    if (q % 2 == 0) {
      long long d = abs(index - (q / 2));
      if (d < min_d) {
        min_d = d;
        ans = i;
      }
    } else {
      long long d = min(abs(index - q / 2), abs(index - (q + 1) / 2));
      if (d < min_d) {
        min_d = d;
        ans = i;
      }
    }
  }
  return ans;
}
long long solve() {
  long long d = gcd(p, q);
  p /= d;
  q /= d;
  if (q == 1) {
    return a;
  }
  if (b - a < 10000000) {
    return solve0();
  }
  e = inverse(p, q);
  long long left = q / 2;
  long long right = (q + 1) / 2;
  if (q % 2 == 0) {
    long long z = get(q / 2);
    if (z != -1) return z;
    left = q / 2 - 1;
    right = q / 2 + 1;
  }
  while (true) {
    long long c0 = get(left);
    long long c1 = get(right);
    if (c0 != -1 && c1 != -1) {
      return min(c0, c1);
    } else if (c0 != -1) {
      return c0;
    } else if (c1 != -1) {
      return c1;
    }
    ++left;
    --right;
  }
}
int main() {
  int T;
  cin >> T;
  while (T--) {
    input();
    cout << solve() << endl;
  }
  return 0;
}
