#include <bits/stdc++.h>
using namespace std;
long long shin[25];
long long seto(void);
void ayano(long long x, char spliter = '\n');
const long double PI = 3.1415926535897932384626;
long long p, q, pinv;
long long gdelt;
long long gans;
long long blks, blksz, blksz2;
long long rinvs[63405], kinvs[63405];
void solve(long long bse, long long lb, long long rb);
long long gcd(long long a, long long b);
long long exgcd(long long a, long long b, long long &x, long long &y);
long long calcdelt(long long x);
int main(void) {
  int testdatas = seto();
  while (testdatas--) {
    long long a, b;
    a = seto(), b = seto(), p = seto(), q = seto();
    long long g = gcd(p, q);
    p /= g, q /= g;
    if (q == 1) {
      ayano(a);
      continue;
    }
    exgcd(p, q, pinv, g);
    pinv %= q, pinv += q, (((pinv) >= q) ? ((pinv) -= q) : (0));
    long long ad = a / q, bd = b / q;
    blksz = sqrt(q);
    blksz2 = blksz << 1;
    blks = (q + blksz - 1) / blksz;
    gdelt = 1000000009, gans = a;
    for (long long i = 0; i < blksz; i++) rinvs[i] = i * pinv % q;
    for (long long i = 0; i < blksz; i++) rinvs[i + blksz] = rinvs[i] - q;
    sort(rinvs, rinvs + blksz2);
    for (long long i = 0; i <= blks; i++) kinvs[i] = i * pinv % q * blksz % q;
    if (ad == bd) {
      solve(ad * q, a % q, b % q);
      ayano(gans);
      continue;
    }
    if (ad + 1 == bd) {
      solve(ad * q, a % q, q - 1);
      solve(ad * q + q, 0, b % q);
      ayano(gans);
      continue;
    }
    solve(ad * q, a % q, q - 1);
    solve(ad * q + q, 0, q - 1);
    ayano(gans);
  }
  return 0;
}
void solve(long long bse, long long lb, long long rb) {
  if (lb > rb) return;
  long long lbbel = lb / blksz;
  long long rbbel = rb / blksz;
  long long tdelt = 1000000009, tdelti = lb;
  if (lbbel == rbbel) {
    for (long long i = lb; i <= rb; i++) {
      long long u = i * p % q;
      u = calcdelt(u);
      (u < tdelt) ? (tdelt = u, tdelti = i) : (0);
    }
    (tdelt < gdelt) ? (gdelt = tdelt, gans = tdelti + bse) : (0);
    (tdelt == gdelt && tdelti + bse < gans) ? (gans = tdelti + bse) : (0);
    return;
  }
  long long tl = q / 2;
  long long lbk = tl / blksz;
  long long rbk = lbk + 1;
  {
    for (long long i = lbk * blksz, ub = lbk * blksz + blksz; i <= ub; i++) {
      long long ux = i * pinv % q;
      if (ux < lb || ux > rb) continue;
      long long ttd = calcdelt(i);
      ux += bse;
      (ttd < gdelt) ? (gdelt = ttd, gans = ux) : (0);
      (ttd == gdelt && ux < gans) ? (gans = ux) : (0);
    }
    lbk--;
  }
  while (1) {
    if (lbk < 0) break;
    if (upper_bound(rinvs, rinvs + blksz2, rb - kinvs[lbk]) -
        lower_bound(rinvs, rinvs + blksz2, lb - kinvs[lbk]))
      break;
    lbk--;
  }
  while (1) {
    if (rbk > blks) break;
    if (upper_bound(rinvs, rinvs + blksz2, rb - kinvs[rbk]) -
        lower_bound(rinvs, rinvs + blksz2, lb - kinvs[rbk]))
      break;
    rbk++;
  }
  if (lbk >= 0) {
    for (long long i = lbk * blksz, ub = lbk * blksz + blksz; i <= ub; i++) {
      long long ux = i * pinv % q;
      if (ux < lb || ux > rb) continue;
      long long ttd = calcdelt(i);
      ux += bse;
      (ttd < gdelt) ? (gdelt = ttd, gans = ux) : (0);
      (ttd == gdelt && ux < gans) ? (gans = ux) : (0);
    }
  }
  if (rbk <= blks) {
    for (long long i = rbk * blksz, ub = rbk * blksz + blksz; i <= ub; i++) {
      long long ux = i * pinv % q;
      if (ux < lb || ux > rb) continue;
      long long ttd = calcdelt(i);
      ux += bse;
      (ttd < gdelt) ? (gdelt = ttd, gans = ux) : (0);
      (ttd == gdelt && ux < gans) ? (gans = ux) : (0);
    }
  }
}
long long gcd(long long a, long long b) {
  long long t;
  while (b) t = a, a = b, b = t % b;
  return 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 qq = a / b;
  long long r = a - qq * b;
  long long g = exgcd(b, r, x, y);
  r = x - qq * y, x = y, y = r;
  return g;
}
inline long long calcdelt(long long x) {
  if (q & 1) {
    long long qq = q >> 1;
    long long ans = x - qq;
    (ans < 0) ? (ans = -ans) : (0);
    long long aans = x - qq - 1;
    (aans < 0) ? (aans = -aans) : (0);
    return (ans < aans) ? (ans) : (aans);
  }
  long long ans = x - (q >> 1);
  (ans < 0) ? (ans = -ans) : (0);
  return ans;
}
long long seto(void) {
  long long x = 0;
  int symbol = 0;
  char ch = getchar();
  while (!isdigit(ch)) (ch == '-') ? (symbol = 1) : (0), ch = getchar();
  while (isdigit(ch)) x = x * 10 + (ch - '0'), ch = getchar();
  return (symbol) ? (-x) : (x);
}
void ayano(long long x, char spliter) {
  if (!x) {
    putchar('0'), putchar(spliter);
    return;
  }
  if (x < 0) putchar('-'), x = -x;
  int len = 0;
  while (x) {
    long long d = x / 10;
    shin[len++] = x - d * 10;
    x = d;
  }
  while (len--) putchar(shin[len] + '0');
  putchar(spliter);
}

### Prompt

Construct a CPP code solution to the problem outlined:

You have given integers a, b, p, and q. Let f(x) = abs(sin(p/q π x)).

Find minimum possible integer x that maximizes f(x) where a ≤ x ≤ b.

Input

Each test contains multiple test cases. 

The first line contains the number of test cases t (1 ≤ t ≤ 100) — the number of test cases.

The first line of each test case contains four integers a, b, p, and q (0 ≤ a ≤ b ≤ 10^{9}, 1 ≤ p, q ≤ 10^{9}).

Output

Print the minimum possible integer x for each test cases, separated by newline.

Example

Input


2
0 3 1 3
17 86 389 995


Output


1
55

Note

In the first test case, f(0) = 0, f(1) = f(2) ≈ 0.866, f(3) = 0.

In the second test case, f(55) ≈ 0.999969, which is the largest among all possible values.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long shin[25];
long long seto(void);
void ayano(long long x, char spliter = '\n');
const long double PI = 3.1415926535897932384626;
long long p, q, pinv;
long long gdelt;
long long gans;
long long blks, blksz, blksz2;
long long rinvs[63405], kinvs[63405];
void solve(long long bse, long long lb, long long rb);
long long gcd(long long a, long long b);
long long exgcd(long long a, long long b, long long &x, long long &y);
long long calcdelt(long long x);
int main(void) {
  int testdatas = seto();
  while (testdatas--) {
    long long a, b;
    a = seto(), b = seto(), p = seto(), q = seto();
    long long g = gcd(p, q);
    p /= g, q /= g;
    if (q == 1) {
      ayano(a);
      continue;
    }
    exgcd(p, q, pinv, g);
    pinv %= q, pinv += q, (((pinv) >= q) ? ((pinv) -= q) : (0));
    long long ad = a / q, bd = b / q;
    blksz = sqrt(q);
    blksz2 = blksz << 1;
    blks = (q + blksz - 1) / blksz;
    gdelt = 1000000009, gans = a;
    for (long long i = 0; i < blksz; i++) rinvs[i] = i * pinv % q;
    for (long long i = 0; i < blksz; i++) rinvs[i + blksz] = rinvs[i] - q;
    sort(rinvs, rinvs + blksz2);
    for (long long i = 0; i <= blks; i++) kinvs[i] = i * pinv % q * blksz % q;
    if (ad == bd) {
      solve(ad * q, a % q, b % q);
      ayano(gans);
      continue;
    }
    if (ad + 1 == bd) {
      solve(ad * q, a % q, q - 1);
      solve(ad * q + q, 0, b % q);
      ayano(gans);
      continue;
    }
    solve(ad * q, a % q, q - 1);
    solve(ad * q + q, 0, q - 1);
    ayano(gans);
  }
  return 0;
}
void solve(long long bse, long long lb, long long rb) {
  if (lb > rb) return;
  long long lbbel = lb / blksz;
  long long rbbel = rb / blksz;
  long long tdelt = 1000000009, tdelti = lb;
  if (lbbel == rbbel) {
    for (long long i = lb; i <= rb; i++) {
      long long u = i * p % q;
      u = calcdelt(u);
      (u < tdelt) ? (tdelt = u, tdelti = i) : (0);
    }
    (tdelt < gdelt) ? (gdelt = tdelt, gans = tdelti + bse) : (0);
    (tdelt == gdelt && tdelti + bse < gans) ? (gans = tdelti + bse) : (0);
    return;
  }
  long long tl = q / 2;
  long long lbk = tl / blksz;
  long long rbk = lbk + 1;
  {
    for (long long i = lbk * blksz, ub = lbk * blksz + blksz; i <= ub; i++) {
      long long ux = i * pinv % q;
      if (ux < lb || ux > rb) continue;
      long long ttd = calcdelt(i);
      ux += bse;
      (ttd < gdelt) ? (gdelt = ttd, gans = ux) : (0);
      (ttd == gdelt && ux < gans) ? (gans = ux) : (0);
    }
    lbk--;
  }
  while (1) {
    if (lbk < 0) break;
    if (upper_bound(rinvs, rinvs + blksz2, rb - kinvs[lbk]) -
        lower_bound(rinvs, rinvs + blksz2, lb - kinvs[lbk]))
      break;
    lbk--;
  }
  while (1) {
    if (rbk > blks) break;
    if (upper_bound(rinvs, rinvs + blksz2, rb - kinvs[rbk]) -
        lower_bound(rinvs, rinvs + blksz2, lb - kinvs[rbk]))
      break;
    rbk++;
  }
  if (lbk >= 0) {
    for (long long i = lbk * blksz, ub = lbk * blksz + blksz; i <= ub; i++) {
      long long ux = i * pinv % q;
      if (ux < lb || ux > rb) continue;
      long long ttd = calcdelt(i);
      ux += bse;
      (ttd < gdelt) ? (gdelt = ttd, gans = ux) : (0);
      (ttd == gdelt && ux < gans) ? (gans = ux) : (0);
    }
  }
  if (rbk <= blks) {
    for (long long i = rbk * blksz, ub = rbk * blksz + blksz; i <= ub; i++) {
      long long ux = i * pinv % q;
      if (ux < lb || ux > rb) continue;
      long long ttd = calcdelt(i);
      ux += bse;
      (ttd < gdelt) ? (gdelt = ttd, gans = ux) : (0);
      (ttd == gdelt && ux < gans) ? (gans = ux) : (0);
    }
  }
}
long long gcd(long long a, long long b) {
  long long t;
  while (b) t = a, a = b, b = t % b;
  return 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 qq = a / b;
  long long r = a - qq * b;
  long long g = exgcd(b, r, x, y);
  r = x - qq * y, x = y, y = r;
  return g;
}
inline long long calcdelt(long long x) {
  if (q & 1) {
    long long qq = q >> 1;
    long long ans = x - qq;
    (ans < 0) ? (ans = -ans) : (0);
    long long aans = x - qq - 1;
    (aans < 0) ? (aans = -aans) : (0);
    return (ans < aans) ? (ans) : (aans);
  }
  long long ans = x - (q >> 1);
  (ans < 0) ? (ans = -ans) : (0);
  return ans;
}
long long seto(void) {
  long long x = 0;
  int symbol = 0;
  char ch = getchar();
  while (!isdigit(ch)) (ch == '-') ? (symbol = 1) : (0), ch = getchar();
  while (isdigit(ch)) x = x * 10 + (ch - '0'), ch = getchar();
  return (symbol) ? (-x) : (x);
}
void ayano(long long x, char spliter) {
  if (!x) {
    putchar('0'), putchar(spliter);
    return;
  }
  if (x < 0) putchar('-'), x = -x;
  int len = 0;
  while (x) {
    long long d = x / 10;
    shin[len++] = x - d * 10;
    x = d;
  }
  while (len--) putchar(shin[len] + '0');
  putchar(spliter);
}

```