#include <bits/stdc++.h>
using namespace std;
const int rootN = 4e4;
set<pair<long long, long long> > s;
set<pair<long long, long long> >::iterator it;
set<long long> taken;
long long a, b, p, q, lim, ans, diff, srch, toadd;
void solve() {
  diff = LLONG_MAX;
  toadd = 0;
  s.clear();
  taken.clear();
  cin >> a >> b >> p >> q;
  lim = min(b, a + rootN - 1);
  for (long long i = a; i <= lim; i++) {
    long long val = (2 * p * i) % (2 * q);
    if (taken.find(val) != taken.end()) continue;
    taken.insert(val);
    s.insert({val, i});
  }
  srch = q;
  while ((a + rootN - 1) <= b) {
    it = s.lower_bound({srch, -1});
    if (it != s.end()) {
      long long td = it->first - srch;
      if (td < diff) {
        diff = td;
        ans = it->second + toadd;
      } else if (td == diff) {
        ans = min(ans, it->second + toadd);
      }
    }
    if (it != s.begin()) {
      it--;
      long long td = abs(it->first - srch);
      if (td < diff) {
        diff = td;
        ans = it->second + toadd;
      } else if (td == diff) {
        ans = min(ans, it->second + toadd);
      }
    }
    toadd += rootN;
    srch = srch - 2 * p * rootN;
    srch %= (2 * q);
    srch = (srch + 2 * q) % (2 * q);
    a += rootN;
  }
  for (long long i = a; i <= b; i++) {
    long long td = (2 * p * i) % (2 * q);
    td = abs(td - q);
    if (td < diff) {
      diff = td;
      ans = i;
    }
  }
  cout << ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  int t;
  cin >> t;
  while (t--) {
    solve();
    cout << '\n';
  }
  return 0;
}
