#include <bits/stdc++.h>
using namespace std;
const int B = 33333;
int T;
long long a, b, p, q;
long long mod;
map<long long, long long> mp;
int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%lld%lld%lld%lld", &a, &b, &p, &q);
    mod = q * 2;
    b -= a;
    mp.clear();
    for (int i = B - 1; i >= 0; i--) {
      long long x = 2 * p * i % mod;
      mp[x] = i;
    }
    long long ax = 2 * p * a % mod;
    long long ans = q + 1, px;
    int i;
    for (i = 0; i * B + B - 1 <= b; i++) {
      long long bx = 2 * p * i * B % mod;
      long long tx = (ax + bx) % mod;
      long long dx = (q + mod - tx) % mod;
      auto it = mp.upper_bound(dx);
      if (it != mp.begin()) {
        it--;
        long long res = (tx + (*it).first) % mod;
        if (abs(res - q) < ans) ans = abs(res - q), px = i * B + (*it).second;
      }
      it = mp.lower_bound(dx);
      if (it != mp.end()) {
        long long res = (tx + (*it).first) % mod;
        if (abs(res - q) < ans)
          ans = abs(res - q), px = i * B + (*it).second;
        else if (abs(res - q) == ans)
          px = min(px, i * B + (*it).second);
      }
    }
    for (int j = i * B; j <= b; j++) {
      long long tx = (ax + 2 * p * j) % mod;
      if (abs(tx - q) < ans) ans = abs(tx - q), px = j;
    }
    printf("%lld\n", px + a);
  }
  return 0;
}
