#include <bits/stdc++.h>
using namespace std;
const int maxn = 200005;
const int maxm = 379;
const int maxlog = 64;
const int inf = 2147483647;
const double eps = 1e-9;
const long long INF = 9223372036854775807ll;
long long qpow(long long a, long long b, long long c) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % c;
    a = a * a % c;
    b >>= 1;
  }
  return ans;
}
inline void rd(int *x) {
  int k, m = 0;
  *x = 0;
  for (;;) {
    (k) = getchar();
    if (k == '-') {
      m = 1;
      break;
    }
    if ('0' <= k && k <= '9') {
      *x = k - '0';
      break;
    }
  }
  for (;;) {
    (k) = getchar();
    if (k < '0' || k > '9') break;
    *x = (*x) * 10 + k - '0';
  }
  if (m) (*x) = -(*x);
}
inline void rd(unsigned int *x) {
  int k, m = 0;
  *x = 0;
  for (;;) {
    (k) = getchar();
    if (k == '-') {
      m = 1;
      break;
    }
    if ('0' <= k && k <= '9') {
      *x = k - '0';
      break;
    }
  }
  for (;;) {
    (k) = getchar();
    if (k < '0' || k > '9') break;
    *x = (*x) * 10 + k - '0';
  }
  if (m) (*x) = -(*x);
}
inline void rd(long long *x) {
  int k, m = 0;
  *x = 0;
  for (;;) {
    (k) = getchar();
    if (k == '-') {
      m = 1;
      break;
    }
    if ('0' <= k && k <= '9') {
      *x = k - '0';
      break;
    }
  }
  for (;;) {
    (k) = getchar();
    if (k < '0' || k > '9') break;
    *x = (*x) * 10 + k - '0';
  }
  if (m) (*x) = -(*x);
}
inline void rd(unsigned long long *x) {
  int k, m = 0;
  *x = 0;
  for (;;) {
    (k) = getchar();
    if (k == '-') {
      m = 1;
      break;
    }
    if ('0' <= k && k <= '9') {
      *x = k - '0';
      break;
    }
  }
  for (;;) {
    (k) = getchar();
    if (k < '0' || k > '9') break;
    *x = (*x) * 10 + k - '0';
  }
  if (m) (*x) = -(*x);
}
inline void rd(double *x) { scanf("%lf", x); }
inline int rd(char c[]) {
  scanf("%s", c);
  return strlen(c);
}
inline void rd(int a[], int n) {
  for (register int i = (0); i < (n); ++i) rd(&a[i]);
}
inline void rd(long long a[], int n) {
  for (register int i = (0); i < (n); ++i) rd(&a[i]);
}
template <class T, class S>
inline void rd(T *x, S *y) {
  rd(x);
  rd(y);
}
template <class T, class S, class U>
inline void rd(T *x, S *y, U *z) {
  rd(x);
  rd(y);
  rd(z);
}
template <class T, class S, class U, class V>
inline void rd(T *x, S *y, U *z, V *w) {
  rd(x);
  rd(y);
  rd(z);
  rd(w);
}
template <class T, class S, class U, class V, class H>
inline void rd(T *x, S *y, U *z, V *w, H *h) {
  rd(x);
  rd(y);
  rd(z);
  rd(w);
  rd(h);
}
template <class T, class S, class U, class V, class H, class J>
inline void rd(T *x, S *y, U *z, V *w, H *h, J *j) {
  rd(x);
  rd(y);
  rd(z);
  rd(w);
  rd(h);
  rd(j);
}
inline void wr(int x) {
  if (x < 10)
    putchar('0' + x);
  else
    wr(x / 10), wr(x % 10);
}
inline void wr(unsigned int x) {
  if (x < 10)
    putchar('0' + x);
  else
    wr(x / 10), wr(x % 10);
}
inline void wr(unsigned long long x) {
  if (x < 10)
    putchar('0' + x);
  else
    wr(x / 10), wr(x % 10);
}
inline void wr(int x, char c) {
  int s = 0, m = 0;
  char f[10];
  if (x < 0) m = 1, x = -x;
  while (x) f[s++] = x % 10, x /= 10;
  if (!s) f[s++] = 0;
  if (m) putchar('-');
  while (s--) putchar(f[s] + '0');
  putchar(c);
}
inline void wr(unsigned int x, char c) {
  int s = 0, m = 0;
  char f[10];
  if (x < 0) m = 1, x = -x;
  while (x) f[s++] = x % 10, x /= 10;
  if (!s) f[s++] = 0;
  if (m) putchar('-');
  while (s--) putchar(f[s] + '0');
  putchar(c);
}
inline void wr(long long x, char c) {
  int s = 0, m = 0;
  char f[20];
  if (x < 0) m = 1, x = -x;
  while (x) f[s++] = x % 10, x /= 10;
  if (!s) f[s++] = 0;
  if (m) putchar('-');
  while (s--) putchar(f[s] + '0');
  putchar(c);
}
inline void wr(unsigned long long x, char c) {
  int s = 0, m = 0;
  char f[20];
  if (x < 0) m = 1, x = -x;
  while (x) f[s++] = x % 10, x /= 10;
  if (!s) f[s++] = 0;
  if (m) putchar('-');
  while (s--) putchar(f[s] + '0');
  putchar(c);
}
inline void wr(double x, char c) {
  printf("%.15f", x);
  putchar(c);
}
inline void wr(const char c[]) {
  int i;
  for (i = 0; c[i] != '\0'; i++) putchar(c[i]);
}
inline void wr(const char x[], char c) {
  int i;
  for (i = 0; x[i] != '\0'; i++) putchar(x[i]);
  putchar(c);
}
template <class T>
inline void wrn(T x) {
  wr(x, '\n');
}
template <class T, class S>
inline void wrn(T x, S y) {
  wr(x, ' ');
  wr(y, '\n');
}
template <class T, class S, class U>
inline void wrn(T x, S y, U z) {
  wr(x, ' ');
  wr(y, ' ');
  wr(z, '\n');
}
template <class T, class S, class U, class H>
inline void wrn(T x, S y, U z, H h) {
  wr(x, ' ');
  wr(y, ' ');
  wr(z, ' ');
  wr(h, '\n');
}
template <class T, class S, class U, class H, class J>
inline void wrn(T x, S y, U z, H h, J j) {
  wr(x, ' ');
  wr(y, ' ');
  wr(z, ' ');
  wr(h, ' ');
  wr(j, '\n');
}
template <class T, class S, class U, class H, class J, class K>
inline void wrn(T x, S y, U z, H h, J j, K k) {
  wr(x, ' ');
  wr(y, ' ');
  wr(z, ' ');
  wr(h, ' ');
  wr(j, ' ');
  wr(k, '\n');
}
template <class T>
inline void wra(T x[], int n) {
  int i;
  if (!n) {
    putchar('\n');
    return;
  }
  for (register int i = (0); i < (n - 1); ++i) wr(x[i], ' ');
  wr(x[n - 1], '\n');
}
long long sm(long long n) { return n * (n + 1) / 2; }
long long sqr(long long n) { return n * n; }
int sgn(long long n) { return (n < 0 ? -1 : 1); }
long long f(long long a, long long b, long long c, long long n) {
  if (!a) return b / c * (n + 1);
  if (!n) return b / c;
  if (a >= c || b >= c)
    return a / c * sm(n) + b / c * (n + 1) + f(a % c, b % c, c, n);
  long long m = (a * n + b) / c;
  return n * m - f(c, c - b - 1, a, m - 1);
}
long long a, b, p, q;
bool check(long long l, long long r) {
  long long sm1 =
      a ? f(2 * p, 2 * q - l, 2 * q, b) - f(2 * p, 2 * q - l, 2 * q, a - 1)
        : f(2 * p, 2 * q - l, 2 * q, b);
  long long sm2 = a ? f(2 * p, 2 * q - r - 1, 2 * q, b) -
                          f(2 * p, 2 * q - r - 1, 2 * q, a - 1)
                    : f(2 * p, 2 * q - r - 1, 2 * q, b);
  if (sm1 - sm2 > 0) return true;
  return false;
}
long long cel(long long a, long long b) {
  if (a % b == 0) return a / b;
  if (sgn(a) * sgn(b) < 0) return a / b;
  return a / b + 1;
}
long long cdl(long long a, long long b) {
  if (a % b == 0) return a / b;
  if (sgn(a) * sgn(b) < 0) return a / b - 1;
  return a / b;
}
long long exgcd(long long a, long long b, long long &x, long long &y) {
  long long ans;
  if (!b)
    ans = a, x = 1, y = 0;
  else
    ans = exgcd(b, a % b, y, x), y -= a / b * x;
  return ans;
}
int main() {
  int t;
  rd(&t);
  while (t--) {
    rd(&a, &b, &p, &q);
    long long l = 0, r = q, d = -1, ans;
    while (l <= r) {
      long long mid = l + r >> 1;
      if (check(q - mid, q + mid)) {
        r = mid - 1;
        d = mid;
      } else {
        l = mid + 1;
      }
    }
    long long res = q - d, x, y, ans1 = INF, ans2 = INF;
    long long dd = exgcd(2 * p, 2 * q, x, y);
    if (res % dd == 0) {
      ans1 = x * res / dd;
      ans1 += cel(a - ans1, 2 * q / (dd)) * (2 * q / (dd));
      if (ans1 > b) ans1 = INF;
    }
    res = q + d;
    if (res % dd == 0) {
      ans2 = x * res / dd;
      ans2 += cel(a - ans2, 2 * q / (dd)) * (2 * q / dd);
      if (ans2 > b) ans2 = INF;
    }
    ans = min(ans1, ans2);
    wrn(ans);
  }
}

### Prompt

Create a solution in Cpp for 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;
const int maxn = 200005;
const int maxm = 379;
const int maxlog = 64;
const int inf = 2147483647;
const double eps = 1e-9;
const long long INF = 9223372036854775807ll;
long long qpow(long long a, long long b, long long c) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % c;
    a = a * a % c;
    b >>= 1;
  }
  return ans;
}
inline void rd(int *x) {
  int k, m = 0;
  *x = 0;
  for (;;) {
    (k) = getchar();
    if (k == '-') {
      m = 1;
      break;
    }
    if ('0' <= k && k <= '9') {
      *x = k - '0';
      break;
    }
  }
  for (;;) {
    (k) = getchar();
    if (k < '0' || k > '9') break;
    *x = (*x) * 10 + k - '0';
  }
  if (m) (*x) = -(*x);
}
inline void rd(unsigned int *x) {
  int k, m = 0;
  *x = 0;
  for (;;) {
    (k) = getchar();
    if (k == '-') {
      m = 1;
      break;
    }
    if ('0' <= k && k <= '9') {
      *x = k - '0';
      break;
    }
  }
  for (;;) {
    (k) = getchar();
    if (k < '0' || k > '9') break;
    *x = (*x) * 10 + k - '0';
  }
  if (m) (*x) = -(*x);
}
inline void rd(long long *x) {
  int k, m = 0;
  *x = 0;
  for (;;) {
    (k) = getchar();
    if (k == '-') {
      m = 1;
      break;
    }
    if ('0' <= k && k <= '9') {
      *x = k - '0';
      break;
    }
  }
  for (;;) {
    (k) = getchar();
    if (k < '0' || k > '9') break;
    *x = (*x) * 10 + k - '0';
  }
  if (m) (*x) = -(*x);
}
inline void rd(unsigned long long *x) {
  int k, m = 0;
  *x = 0;
  for (;;) {
    (k) = getchar();
    if (k == '-') {
      m = 1;
      break;
    }
    if ('0' <= k && k <= '9') {
      *x = k - '0';
      break;
    }
  }
  for (;;) {
    (k) = getchar();
    if (k < '0' || k > '9') break;
    *x = (*x) * 10 + k - '0';
  }
  if (m) (*x) = -(*x);
}
inline void rd(double *x) { scanf("%lf", x); }
inline int rd(char c[]) {
  scanf("%s", c);
  return strlen(c);
}
inline void rd(int a[], int n) {
  for (register int i = (0); i < (n); ++i) rd(&a[i]);
}
inline void rd(long long a[], int n) {
  for (register int i = (0); i < (n); ++i) rd(&a[i]);
}
template <class T, class S>
inline void rd(T *x, S *y) {
  rd(x);
  rd(y);
}
template <class T, class S, class U>
inline void rd(T *x, S *y, U *z) {
  rd(x);
  rd(y);
  rd(z);
}
template <class T, class S, class U, class V>
inline void rd(T *x, S *y, U *z, V *w) {
  rd(x);
  rd(y);
  rd(z);
  rd(w);
}
template <class T, class S, class U, class V, class H>
inline void rd(T *x, S *y, U *z, V *w, H *h) {
  rd(x);
  rd(y);
  rd(z);
  rd(w);
  rd(h);
}
template <class T, class S, class U, class V, class H, class J>
inline void rd(T *x, S *y, U *z, V *w, H *h, J *j) {
  rd(x);
  rd(y);
  rd(z);
  rd(w);
  rd(h);
  rd(j);
}
inline void wr(int x) {
  if (x < 10)
    putchar('0' + x);
  else
    wr(x / 10), wr(x % 10);
}
inline void wr(unsigned int x) {
  if (x < 10)
    putchar('0' + x);
  else
    wr(x / 10), wr(x % 10);
}
inline void wr(unsigned long long x) {
  if (x < 10)
    putchar('0' + x);
  else
    wr(x / 10), wr(x % 10);
}
inline void wr(int x, char c) {
  int s = 0, m = 0;
  char f[10];
  if (x < 0) m = 1, x = -x;
  while (x) f[s++] = x % 10, x /= 10;
  if (!s) f[s++] = 0;
  if (m) putchar('-');
  while (s--) putchar(f[s] + '0');
  putchar(c);
}
inline void wr(unsigned int x, char c) {
  int s = 0, m = 0;
  char f[10];
  if (x < 0) m = 1, x = -x;
  while (x) f[s++] = x % 10, x /= 10;
  if (!s) f[s++] = 0;
  if (m) putchar('-');
  while (s--) putchar(f[s] + '0');
  putchar(c);
}
inline void wr(long long x, char c) {
  int s = 0, m = 0;
  char f[20];
  if (x < 0) m = 1, x = -x;
  while (x) f[s++] = x % 10, x /= 10;
  if (!s) f[s++] = 0;
  if (m) putchar('-');
  while (s--) putchar(f[s] + '0');
  putchar(c);
}
inline void wr(unsigned long long x, char c) {
  int s = 0, m = 0;
  char f[20];
  if (x < 0) m = 1, x = -x;
  while (x) f[s++] = x % 10, x /= 10;
  if (!s) f[s++] = 0;
  if (m) putchar('-');
  while (s--) putchar(f[s] + '0');
  putchar(c);
}
inline void wr(double x, char c) {
  printf("%.15f", x);
  putchar(c);
}
inline void wr(const char c[]) {
  int i;
  for (i = 0; c[i] != '\0'; i++) putchar(c[i]);
}
inline void wr(const char x[], char c) {
  int i;
  for (i = 0; x[i] != '\0'; i++) putchar(x[i]);
  putchar(c);
}
template <class T>
inline void wrn(T x) {
  wr(x, '\n');
}
template <class T, class S>
inline void wrn(T x, S y) {
  wr(x, ' ');
  wr(y, '\n');
}
template <class T, class S, class U>
inline void wrn(T x, S y, U z) {
  wr(x, ' ');
  wr(y, ' ');
  wr(z, '\n');
}
template <class T, class S, class U, class H>
inline void wrn(T x, S y, U z, H h) {
  wr(x, ' ');
  wr(y, ' ');
  wr(z, ' ');
  wr(h, '\n');
}
template <class T, class S, class U, class H, class J>
inline void wrn(T x, S y, U z, H h, J j) {
  wr(x, ' ');
  wr(y, ' ');
  wr(z, ' ');
  wr(h, ' ');
  wr(j, '\n');
}
template <class T, class S, class U, class H, class J, class K>
inline void wrn(T x, S y, U z, H h, J j, K k) {
  wr(x, ' ');
  wr(y, ' ');
  wr(z, ' ');
  wr(h, ' ');
  wr(j, ' ');
  wr(k, '\n');
}
template <class T>
inline void wra(T x[], int n) {
  int i;
  if (!n) {
    putchar('\n');
    return;
  }
  for (register int i = (0); i < (n - 1); ++i) wr(x[i], ' ');
  wr(x[n - 1], '\n');
}
long long sm(long long n) { return n * (n + 1) / 2; }
long long sqr(long long n) { return n * n; }
int sgn(long long n) { return (n < 0 ? -1 : 1); }
long long f(long long a, long long b, long long c, long long n) {
  if (!a) return b / c * (n + 1);
  if (!n) return b / c;
  if (a >= c || b >= c)
    return a / c * sm(n) + b / c * (n + 1) + f(a % c, b % c, c, n);
  long long m = (a * n + b) / c;
  return n * m - f(c, c - b - 1, a, m - 1);
}
long long a, b, p, q;
bool check(long long l, long long r) {
  long long sm1 =
      a ? f(2 * p, 2 * q - l, 2 * q, b) - f(2 * p, 2 * q - l, 2 * q, a - 1)
        : f(2 * p, 2 * q - l, 2 * q, b);
  long long sm2 = a ? f(2 * p, 2 * q - r - 1, 2 * q, b) -
                          f(2 * p, 2 * q - r - 1, 2 * q, a - 1)
                    : f(2 * p, 2 * q - r - 1, 2 * q, b);
  if (sm1 - sm2 > 0) return true;
  return false;
}
long long cel(long long a, long long b) {
  if (a % b == 0) return a / b;
  if (sgn(a) * sgn(b) < 0) return a / b;
  return a / b + 1;
}
long long cdl(long long a, long long b) {
  if (a % b == 0) return a / b;
  if (sgn(a) * sgn(b) < 0) return a / b - 1;
  return a / b;
}
long long exgcd(long long a, long long b, long long &x, long long &y) {
  long long ans;
  if (!b)
    ans = a, x = 1, y = 0;
  else
    ans = exgcd(b, a % b, y, x), y -= a / b * x;
  return ans;
}
int main() {
  int t;
  rd(&t);
  while (t--) {
    rd(&a, &b, &p, &q);
    long long l = 0, r = q, d = -1, ans;
    while (l <= r) {
      long long mid = l + r >> 1;
      if (check(q - mid, q + mid)) {
        r = mid - 1;
        d = mid;
      } else {
        l = mid + 1;
      }
    }
    long long res = q - d, x, y, ans1 = INF, ans2 = INF;
    long long dd = exgcd(2 * p, 2 * q, x, y);
    if (res % dd == 0) {
      ans1 = x * res / dd;
      ans1 += cel(a - ans1, 2 * q / (dd)) * (2 * q / (dd));
      if (ans1 > b) ans1 = INF;
    }
    res = q + d;
    if (res % dd == 0) {
      ans2 = x * res / dd;
      ans2 += cel(a - ans2, 2 * q / (dd)) * (2 * q / dd);
      if (ans2 > b) ans2 = INF;
    }
    ans = min(ans1, ans2);
    wrn(ans);
  }
}

```