#include <bits/stdc++.h>
using namespace std;
long long a, b, p, q;
long long g(long long x) { return (2 * p * x) % (2 * q); }
void solve() {
  cin >> a >> b >> p >> q;
  b++;
  long long siz = 1;
  while (siz * siz < b - a) siz++;
  vector<pair<long long, long long> > ar, br;
  for (int i = a; i < a + siz; i++) {
    br.push_back({g(i), i});
  }
  sort(br.begin(), br.end());
  ar.push_back(br[0]);
  for (int i = 1; i < br.size(); i++) {
    if (br[i].first != br[i - 1].first) {
      ar.push_back(br[i]);
    }
  }
  long long minval = 1e14, minind;
  long long i = 0;
  for (i = 0; a + ((i + 1) * siz) <= b; i++) {
    long long look = q - g(i * siz);
    look % (2 * q);
    if (look < 0) look += 2 * q;
    long long ans =
        lower_bound(ar.begin(), ar.end(), make_pair(look, (long long)-1e14)) -
        ar.begin();
    for (long long j = 0; j >= -1; j--) {
      long long ans2 = (ans + j) % ar.size();
      if (ans2 < 0) ans2 += ar.size();
      long long val = abs(look - ar[ans2].first);
      if (val > q) val = 2 * q - val;
      long long ind = ar[ans2].second + (i * siz);
      if (make_pair(minval, minind) > make_pair(val, ind)) {
        minval = val;
        minind = ind;
      }
    }
  }
  for (i = a + (i * siz); i < b; i++) {
    long long val = abs(q - g(i));
    long long ind = i;
    if (make_pair(minval, minind) > make_pair(val, ind)) {
      minval = val;
      minind = ind;
    }
  }
  cout << minind << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ;
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
}
