#include <bits/stdc++.h>
using namespace std;
const int tmw168 = 1e5;
long long a, b, p, q, invp;
long long gcd(long long x, long long y) {
  if (y == 0) return x;
  return gcd(y, x % y);
}
long long test(long long r) {
  r = r * invp % q;
  r += a / q * q;
  if (r < a) r += q;
  return r;
}
int f(long long x, long long y) {
  if (min(x, y) > b) return false;
  cout << min(x, y) << '\n';
  return true;
}
long long inv(long long a, long long b) {
  long long s = 0, t = 1;
  long long old_s = 1, old_t = 0;
  long long r = b, old_r = a;
  while (r != 0) {
    long long quotient = old_r / r;
    long long tr = r;
    r = old_r - quotient * r;
    old_r = tr;
    long long ts = s;
    s = old_s - quotient * s;
    old_s = ts;
    long long tt = t;
    t = old_t - quotient * t;
    old_t = tt;
  }
  old_s = (old_s % q + q) % q;
  return old_s;
}
void solve() {
  cin >> a >> b >> p >> q;
  long long g = gcd(p, q);
  p /= g;
  q /= g;
  p %= q;
  int ma = -1, gd = 0;
  if (b - a < tmw168) {
    for (int i = a; i <= b; i++) {
      int cur = min(i * p % q, q - i * p % q);
      if (cur > ma) {
        ma = cur;
        gd = i;
      }
    }
    cout << gd << '\n';
    return;
  }
  invp = inv(p, q);
  for (int i = 0; i < q; i++) {
    if (f(test(q / 2 - i), test((q + 1) / 2 + i))) return;
  }
}
int main() {
  ios::sync_with_stdio(false);
  int t;
  cin >> t;
  while (t--) solve();
}
