#include <bits/stdc++.h>
using namespace std;
inline bool setmin(int &x, int y) { return (y < x) ? x = y, 1 : 0; }
inline bool setmax(int &x, int y) { return (y > x) ? x = y, 1 : 0; }
inline bool setmin(long long &x, long long y) { return (y < x) ? x = y, 1 : 0; }
inline bool setmax(long long &x, long long y) { return (y > x) ? x = y, 1 : 0; }
const int N = 1000000;
const int inf = (int)1e9 + 1;
const long long big = (long long)1e18 + 1;
const int P = 239;
const int P1 = 31;
const int P2 = 57;
const int MOD = (int)1e9 + 7;
const int MOD1 = (int)1e9 + 9;
const int MOD2 = 998244353;
const double eps = 1e-9;
const double pi = atan2(0, -1);
const int ABC = 26;
const int B = 30000;
pair<int, int> del1[B];
int del[B], id[B];
int C;
void init(long long p, long long q) {
  for (int i = 0; i < B; i++) {
    del1[i] = {p * i % q, i};
  }
  sort(del1, del1 + B);
  C = 0;
  for (int i = 0; i < B; i++) {
    if (i == 0 || del1[i].first != del1[i - 1].first) {
      del[C] = del1[i].first;
      id[C] = del1[i].second;
      C++;
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.precision(20);
  cout << fixed;
  int T;
  cin >> T;
  while (T--) {
    long long a, b, p, q;
    cin >> a >> b >> p >> q;
    p %= q;
    long long best = big, ans = -1;
    p *= 2;
    q *= 2;
    init(p, q);
    long long x = a * p % q, cur = a;
    while (cur + B <= b + 1) {
      int pos;
      if (x <= q / 2) {
        pos = lower_bound(del, del + C, q / 2 - x) - del;
      } else {
        pos = lower_bound(del, del + C, q + q / 2 - x) - del;
      }
      if (pos < C) {
        long long v = x + del[pos];
        if (v >= q) {
          v -= q;
        }
        if (abs(q / 2 - v) < best ||
            abs(q / 2 - v) == best && cur + id[pos] < ans) {
          best = abs(q / 2 - v);
          ans = cur + id[pos];
        }
      }
      if (pos - 1 >= 0) {
        pos--;
        long long v = x + del[pos];
        if (v >= q) {
          v -= q;
        }
        if (abs(q / 2 - v) < best ||
            abs(q / 2 - v) == best && cur + id[pos] < ans) {
          best = abs(q / 2 - v);
          ans = cur + id[pos];
        }
      }
      x = (x + p * B) % q;
      cur += B;
    }
    while (cur <= b) {
      if (abs(q / 2 - x) < best) {
        best = abs(q / 2 - x);
        ans = cur;
      }
      x += p;
      if (x >= q) {
        x -= q;
      }
      cur++;
    }
    cout << ans << "\n";
  }
  return 0;
}
