#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline bool upmin(T &x, T y) {
  return y < x ? x = y, 1 : 0;
}
template <typename T>
inline bool upmax(T &x, T y) {
  return x < y ? x = y, 1 : 0;
}
const long double eps = 1e-9;
const long double pi = acos(-1);
const int oo = 1 << 30;
const long long loo = 1ll << 60;
const int mods = 998244353;
const int inv2 = (mods + 1) >> 1;
const int MAXN = 600005;
const int INF = 0x3f3f3f3f;
namespace FastIO {
constexpr int SIZE = (1 << 21) + 1;
int num = 0, f;
char ibuf[SIZE], obuf[SIZE], que[65], *iS, *iT, *oS = obuf,
                                                *oT = obuf + SIZE - 1, c;
inline void flush() {
  fwrite(obuf, 1, oS - obuf, stdout);
  oS = obuf;
}
inline void putc(char c) {
  *oS++ = c;
  if (oS == oT) flush();
}
inline void getc(char &c) {
  for (c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++);
       !isalpha(c) && c != EOF;
       c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    ;
}
inline void reads(char *st) {
  char c;
  int n = 0;
  getc(st[++n]);
  for (c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++);
       isalpha(c);
       c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    st[++n] = c;
}
template <class I>
inline void read(I &x) {
  for (f = 1, c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                              (iS == iT ? EOF : *iS++))
                            : *iS++);
       c < '0' || c > '9';
       c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    if (c == '-') f = -1;
  for (x = 0; c >= '0' && c <= '9';
       c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    x = (x << 3) + (x << 1) + (c & 15);
  x *= f;
}
template <class I>
inline void print(I x) {
  if (x < 0) putc('-'), x = -x;
  if (!x) putc('0');
  while (x) que[++num] = x % 10 + 48, x /= 10;
  while (num) putc(que[num--]);
}
struct Flusher_ {
  ~Flusher_() { flush(); }
} io_Flusher_;
}  // namespace FastIO
using FastIO ::print;
using FastIO ::putc;
using FastIO ::read;
using FastIO ::reads;
long long X, Y, ans, a, b, p, q, P, Q;
long long gcd(long long x, long long y) { return y == 0 ? x : gcd(y, x % y); }
void exgcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) return (void)(x = 1, y = 0);
  exgcd(b, a % b, y, x);
  y -= (a / b) * x;
}
long long solve(long long a, long long b, long long c, long long n) {
  long long ans = 0;
  if (a >= c || b >= c) {
    long long p = a / c, q = b / c;
    ans += n * (n + 1) / 2 * p + q * (n + 1);
    a %= c, b %= c;
  }
  if (!a) return ans;
  long long m = (a * n + b) / c;
  return ans + n * m - solve(c, c - b - 1, a, m - 1);
}
int check(long long x) {
  long long l = q - x, r = q + x;
  return (solve(P, Q - l, Q, b) - solve(P, Q - l, Q, a - 1)) -
             (solve(P, Q - r - 1, Q, b) - solve(P, Q - r - 1, Q, a - 1)) >
         0;
}
signed main() {
  int Case;
  read(Case);
  while (Case--) {
    read(a), read(b), read(p), read(q), P = p << 1, Q = q << 1, ans = loo;
    long long l = 0, r = q;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (check(mid))
        r = mid;
      else
        l = mid + 1;
    }
    long long G = gcd(P, Q);
    P /= G, Q /= G;
    if ((q + r) % G == 0) {
      exgcd(P, Q, X, Y);
      X = (q + r) / G * X % Q;
      X += (a - X) / Q * Q;
      while (X >= a) X -= Q;
      while (X < a) X += Q;
      upmin(ans, X);
    }
    if ((q - r) % G == 0) {
      exgcd(P, Q, X, Y);
      X = (q - r) / G * X % Q;
      X += (a - X) / Q * Q;
      while (X >= a) X -= Q;
      while (X < a) X += Q;
      upmin(ans, X);
    }
    print(ans), putc('\n');
  }
  return 0;
}

### Prompt

Generate a cpp solution to the following problem:

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;
template <typename T>
inline bool upmin(T &x, T y) {
  return y < x ? x = y, 1 : 0;
}
template <typename T>
inline bool upmax(T &x, T y) {
  return x < y ? x = y, 1 : 0;
}
const long double eps = 1e-9;
const long double pi = acos(-1);
const int oo = 1 << 30;
const long long loo = 1ll << 60;
const int mods = 998244353;
const int inv2 = (mods + 1) >> 1;
const int MAXN = 600005;
const int INF = 0x3f3f3f3f;
namespace FastIO {
constexpr int SIZE = (1 << 21) + 1;
int num = 0, f;
char ibuf[SIZE], obuf[SIZE], que[65], *iS, *iT, *oS = obuf,
                                                *oT = obuf + SIZE - 1, c;
inline void flush() {
  fwrite(obuf, 1, oS - obuf, stdout);
  oS = obuf;
}
inline void putc(char c) {
  *oS++ = c;
  if (oS == oT) flush();
}
inline void getc(char &c) {
  for (c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++);
       !isalpha(c) && c != EOF;
       c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    ;
}
inline void reads(char *st) {
  char c;
  int n = 0;
  getc(st[++n]);
  for (c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++);
       isalpha(c);
       c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    st[++n] = c;
}
template <class I>
inline void read(I &x) {
  for (f = 1, c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                              (iS == iT ? EOF : *iS++))
                            : *iS++);
       c < '0' || c > '9';
       c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    if (c == '-') f = -1;
  for (x = 0; c >= '0' && c <= '9';
       c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    x = (x << 3) + (x << 1) + (c & 15);
  x *= f;
}
template <class I>
inline void print(I x) {
  if (x < 0) putc('-'), x = -x;
  if (!x) putc('0');
  while (x) que[++num] = x % 10 + 48, x /= 10;
  while (num) putc(que[num--]);
}
struct Flusher_ {
  ~Flusher_() { flush(); }
} io_Flusher_;
}  // namespace FastIO
using FastIO ::print;
using FastIO ::putc;
using FastIO ::read;
using FastIO ::reads;
long long X, Y, ans, a, b, p, q, P, Q;
long long gcd(long long x, long long y) { return y == 0 ? x : gcd(y, x % y); }
void exgcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) return (void)(x = 1, y = 0);
  exgcd(b, a % b, y, x);
  y -= (a / b) * x;
}
long long solve(long long a, long long b, long long c, long long n) {
  long long ans = 0;
  if (a >= c || b >= c) {
    long long p = a / c, q = b / c;
    ans += n * (n + 1) / 2 * p + q * (n + 1);
    a %= c, b %= c;
  }
  if (!a) return ans;
  long long m = (a * n + b) / c;
  return ans + n * m - solve(c, c - b - 1, a, m - 1);
}
int check(long long x) {
  long long l = q - x, r = q + x;
  return (solve(P, Q - l, Q, b) - solve(P, Q - l, Q, a - 1)) -
             (solve(P, Q - r - 1, Q, b) - solve(P, Q - r - 1, Q, a - 1)) >
         0;
}
signed main() {
  int Case;
  read(Case);
  while (Case--) {
    read(a), read(b), read(p), read(q), P = p << 1, Q = q << 1, ans = loo;
    long long l = 0, r = q;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (check(mid))
        r = mid;
      else
        l = mid + 1;
    }
    long long G = gcd(P, Q);
    P /= G, Q /= G;
    if ((q + r) % G == 0) {
      exgcd(P, Q, X, Y);
      X = (q + r) / G * X % Q;
      X += (a - X) / Q * Q;
      while (X >= a) X -= Q;
      while (X < a) X += Q;
      upmin(ans, X);
    }
    if ((q - r) % G == 0) {
      exgcd(P, Q, X, Y);
      X = (q - r) / G * X % Q;
      X += (a - X) / Q * Q;
      while (X >= a) X -= Q;
      while (X < a) X += Q;
      upmin(ans, X);
    }
    print(ans), putc('\n');
  }
  return 0;
}

```