#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
const double pi = acos(-1.0);
const long long mod = 1000000007;
int T;
long long intg(long long x, long long y, int ty) {
  if (ty == 0) {
    if (x >= 0)
      return x / y;
    else
      return -(-x + y - 1) / y;
  } else {
    if (x >= 0) return (x + y - 1) / y;
    return -(-x) / y;
  }
}
long long solve(long long a, long long b, long long p, long long q, long long A,
                long long B) {
  p = p % q;
  if (p == 0) {
    return intg(A, q, 1) * q <= B ? a : a - 1;
  }
  long long llb = intg(a * p - B, q, 1), lub = intg(b * p - A, q, 0);
  if (lub < llb) return a - 1;
  if (B - A >= p) return max(intg(llb * q + A, p, 1), a);
  long long l = solve(llb, lub, q % p, p, -B, -A);
  if (l < llb) return a - 1;
  return intg(l * q + A, p, 1);
}
int main() {
  ios_base::sync_with_stdio(false);
  int i, j;
  cin >> T;
  while (T--) {
    long long a, b, p, q;
    cin >> a >> b >> p >> q;
    p %= q;
    if (p == 0) {
      cout << a << "\n";
      continue;
    }
    long long lb = 0, ub = q / 2;
    long long tmp = solve(a, b, p, q, ub, q - ub);
    if (tmp >= a)
      cout << tmp << "\n";
    else {
      long long ans = -1;
      while (ub - lb > 1) {
        long long mid = (ub + lb) >> 1;
        tmp = solve(a, b, p, q, mid, q - mid);
        if (tmp >= a)
          ans = tmp, lb = mid;
        else
          ub = mid;
      }
      cout << ans << "\n";
    }
  }
  return 0;
}
