#include <bits/stdc++.h>
template <typename T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  bool flag = false;
  while (!isdigit(c)) {
    if (c == '-') flag = true;
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + (c ^ 48);
    c = getchar();
  }
  if (flag) x = -x;
}
using namespace std;
const long long up = 4e9;
inline void MIN(long long &a, long long b) {
  if (b < a) a = b;
}
long long a, b, p, q, pp, qq;
long long calc(long long n, long long a, long long b, long long c) {
  if (!a) return b / c * (n + 1);
  if (a >= c || b >= c)
    return n * (n + 1) / 2 * (a / c) + (n + 1) * (b / c) +
           calc(n, a % c, b % c, c);
  long long m = (a * n + b) / c;
  return n * m - calc(m - 1, c, c - b - 1, a);
}
inline bool check(long long l, long long r) {
  if (l < 0) l = 0;
  if (r >= qq) r = qq - 1;
  long long tmp1 = calc(b, pp, qq - l, qq) - calc(a - 1, pp, qq - l, qq);
  long long tmp2 =
      calc(b, pp, qq - r - 1, qq) - calc(a - 1, pp, qq - r - 1, qq);
  return tmp1 - tmp2 > 0;
}
long long ans = up;
long long get_gcd(long long a, long long b) {
  return b ? get_gcd(b, a % b) : a;
}
long long exgcd(long long a, long long b, long long &x, long long &y) {
  if (!b) {
    x = 1, y = 0;
    return a;
  }
  long long g = exgcd(b, a % b, x, y);
  long long tmpx = x;
  x = y;
  y = tmpx - a / b * y;
  return g;
}
long long sol(long long a, long long b, long long c) {
  long long g = get_gcd(a, b);
  if (c % g) return -1;
  a /= g;
  b /= g;
  c /= g;
  long long x, y;
  exgcd(a, b, x, y);
  x = (x * c % b + b) % b;
  return x;
}
inline void work(long long jzp) {
  if (jzp < 0) jzp = 0;
  if (jzp >= qq) jzp = qq - 1;
  long long x = sol(pp, qq, jzp);
  if (~x) {
    long long zzz = get_gcd(pp, qq);
    zzz = qq / zzz;
    x += (a / zzz) * zzz;
    while (x < a) x += zzz;
    while (x - zzz >= a) x -= zzz;
    MIN(ans, x);
  }
}
signed main() {
  long long _;
  read(_);
  while (_--) {
    ans = up;
    read(a), read(b), read(p), read(q);
    pp = p + p;
    qq = q + q;
    long long l = 0, r = up, res = up;
    while (l <= r) {
      long long mid = (l + r) >> 1;
      if (check(q - mid, q + mid))
        res = mid, r = mid - 1;
      else
        l = mid + 1;
    }
    work(q - res);
    work(q + res);
    printf("%lld\n", ans);
  }
  return 0;
}
