#include <bits/stdc++.h>
using namespace std;
const long long SQ = 30000;
long long gcd(long long a, long long b) {
  if (!a) return b;
  if (!b) return a;
  return gcd(b, a % b);
}
map<long long, long long> mp;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int N;
  cin >> N;
  while (N--) {
    mp.clear();
    long long a, b, p, q;
    cin >> a >> b >> p >> q;
    long long g = gcd(p, q);
    p /= g;
    q /= g;
    if (b - a > q) {
      b -= ((b - a - q) / q) * q;
    }
    p %= q;
    long long gs = 0;
    for (int i = 0; i < SQ; i++) {
      if (mp.find(gs) != mp.end()) {
        break;
      }
      mp[gs] = i;
      gs = (gs + 2 * p) % (2 * q);
    }
    long long mi = 0, ma = 1LL << 50;
    long long id = a;
    for (; id + SQ <= b; id += SQ) {
      long long hl = ((q - id * 2 * p) % (2 * q));
      if (hl < 0) {
        hl += 2 * q;
      }
      auto it = mp.lower_bound(hl);
      long long ub, lb;
      if (it == mp.end()) {
        ub = mp.begin()->second;
      } else {
        ub = it->second;
      }
      if (it == mp.begin()) {
        lb = mp.rbegin()->second;
      } else {
        lb = (--it)->second;
      }
      long long df = abs((((ub + id) * 2 * p) % (2 * q)) - q);
      if (df < ma) {
        ma = df;
        mi = ub + id;
      }
      df = abs((((lb + id) * 2 * p) % (2 * q)) - q);
      if (df < ma) {
        ma = df;
        mi = lb + id;
      } else if ((df == ma) && (lb + id < mi)) {
        mi = lb + id;
      }
    }
    for (; id <= b; id++) {
      long long df = abs((id * 2 * p) % (2 * q) - q);
      if (df < ma) {
        ma = df;
        mi = id;
      }
    }
    cout << mi << '\n';
  }
}
