#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long x = 0;
  int f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
  return x * f;
}
void print(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) print(x / 10);
  putchar(x % 10 + '0');
}
long long f(long long a, long long b, long long c, long long n) {
  if (!a || !n) return (n + 1) * (b / c);
  if (n < 0) return 0;
  if (a >= c || b >= c)
    return f(a % c, b % c, c, n) + (n * (n + 1) >> 1) * (a / c) +
           (n + 1) * (b / c);
  long long m = (a * n + b) / c;
  return n * m - f(c, c - b - 1, a, m - 1);
}
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, y, x);
  y -= a / b * x;
  return g;
}
long long a, b, p, q;
int main() {
  int T = read();
  while (T--) {
    a = read(), b = read(), p = read(), q = read();
    long long l = 0, r = q, P = p * 2, Q = q * 2, ans;
    while (l <= r) {
      long long mid = l + r >> 1;
      long long L = q - mid, R = q + mid + 1;
      if (f(P, Q - L, Q, b) - f(P, Q - R, Q, b) + f(P, Q - R, Q, a - 1) -
              f(P, Q - L, Q, a - 1) >
          0)
        ans = mid, r = mid - 1;
      else
        l = mid + 1;
    }
    long long x, y, g = exgcd(P, Q, x, y), minn = 1061109567;
    P /= g, Q /= g;
    if ((q - ans) % g == 0) {
      long long xx = (q - ans) / g * x;
      xx += (a - xx) / Q * Q;
      while (xx >= a) xx -= Q;
      while (xx < a) xx += Q;
      minn = min(minn, xx);
    }
    if ((q + ans) % g == 0) {
      long long xx = (q + ans) / g * x;
      xx += (a - xx) / Q * Q;
      while (xx >= a) xx -= Q;
      while (xx < a) xx += Q;
      minn = min(minn, xx);
    }
    print(minn), putchar('\n');
  }
}
