#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) { return !b ? a : gcd(b, a % b); }
long long exgcd(long long a, long long b, long long &x, long long &y) {
  if (!b) {
    x = 1, y = 0;
    return a;
  } else {
    long long g = exgcd(b, a % b, y, x);
    y -= x * (a / b);
    return g;
  }
}
long long a, b, p, q;
long long calc(long long a, long long b, long long c, long long n) {
  if (n < 0) {
    return 0;
  } else if (a == 0) {
    return (n + 1) * (long long)floor(1.0 * b / c);
  } else if (a >= c || b >= c || a < 0 || b < 0) {
    long long t = n * (n + 1) / 2, ta = (long long)floor(1.0 * a / c),
              tb = (long long)floor(1.0 * b / c);
    return t * ta + (n + 1) * tb + calc(a - ta * c, b - tb * c, c, n);
  } else {
    long long m = (long long)floor(1.0 * (a * n + b) / c);
    return n * m - calc(c, c - b - 1, a, m - 1);
  }
}
long long check(long long M) {
  int L = q - M, R = q + M;
  return (calc(p << 1, -L, q << 1, b) - calc(p << 1, -L, q << 1, a - 1)) -
         (calc(p << 1, -(R + 1), q << 1, b) -
          calc(p << 1, -(R + 1), q << 1, a - 1));
}
long long get_ans(long long N) {
  long long ta = p << 1, tb = q << 1, x, y;
  long long g = exgcd(ta, tb, x, y);
  x *= N / g, y *= N / g;
  ta /= g, tb /= g;
  if (x < a) {
    long long t = (a - x - 1) / tb + 1;
    x += t * tb;
    y -= t * ta;
  }
  if (x >= a + tb) {
    long long t = (x - a) / tb;
    x -= t * tb;
    y -= t * ta;
  }
  return x;
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%lld %lld %lld %lld", &a, &b, &p, &q);
    long long L = 0, R = q, minv = 0;
    while (L <= R) {
      long long M = (L + R) >> 1;
      if (check(M)) {
        minv = M;
        R = M - 1;
      } else {
        L = M + 1;
      }
    }
    long long g = gcd(p, q), ans = LONG_LONG_MAX;
    if ((q + minv) % g == 0) {
      ans = min(ans, get_ans(q + minv));
    }
    if ((q - minv) % g == 0) {
      ans = min(ans, get_ans(q - minv));
    }
    printf("%lld\n", ans);
  }
  getchar();
  getchar();
  return 0;
}

### Prompt

Your task is to create 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;
long long gcd(long long a, long long b) { return !b ? a : gcd(b, a % b); }
long long exgcd(long long a, long long b, long long &x, long long &y) {
  if (!b) {
    x = 1, y = 0;
    return a;
  } else {
    long long g = exgcd(b, a % b, y, x);
    y -= x * (a / b);
    return g;
  }
}
long long a, b, p, q;
long long calc(long long a, long long b, long long c, long long n) {
  if (n < 0) {
    return 0;
  } else if (a == 0) {
    return (n + 1) * (long long)floor(1.0 * b / c);
  } else if (a >= c || b >= c || a < 0 || b < 0) {
    long long t = n * (n + 1) / 2, ta = (long long)floor(1.0 * a / c),
              tb = (long long)floor(1.0 * b / c);
    return t * ta + (n + 1) * tb + calc(a - ta * c, b - tb * c, c, n);
  } else {
    long long m = (long long)floor(1.0 * (a * n + b) / c);
    return n * m - calc(c, c - b - 1, a, m - 1);
  }
}
long long check(long long M) {
  int L = q - M, R = q + M;
  return (calc(p << 1, -L, q << 1, b) - calc(p << 1, -L, q << 1, a - 1)) -
         (calc(p << 1, -(R + 1), q << 1, b) -
          calc(p << 1, -(R + 1), q << 1, a - 1));
}
long long get_ans(long long N) {
  long long ta = p << 1, tb = q << 1, x, y;
  long long g = exgcd(ta, tb, x, y);
  x *= N / g, y *= N / g;
  ta /= g, tb /= g;
  if (x < a) {
    long long t = (a - x - 1) / tb + 1;
    x += t * tb;
    y -= t * ta;
  }
  if (x >= a + tb) {
    long long t = (x - a) / tb;
    x -= t * tb;
    y -= t * ta;
  }
  return x;
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%lld %lld %lld %lld", &a, &b, &p, &q);
    long long L = 0, R = q, minv = 0;
    while (L <= R) {
      long long M = (L + R) >> 1;
      if (check(M)) {
        minv = M;
        R = M - 1;
      } else {
        L = M + 1;
      }
    }
    long long g = gcd(p, q), ans = LONG_LONG_MAX;
    if ((q + minv) % g == 0) {
      ans = min(ans, get_ans(q + minv));
    }
    if ((q - minv) % g == 0) {
      ans = min(ans, get_ans(q - minv));
    }
    printf("%lld\n", ans);
  }
  getchar();
  getchar();
  return 0;
}

```