#include <bits/stdc++.h>
using namespace std;
int T, a, b, p, q;
long long f(long long n, long long a, long long b, long long c) {
  if (!a) return b / c * (n + 1);
  if (a >= c || b >= c)
    return f(n, a % c, b % c, c) + n * (n + 1) / 2 * (a / c) +
           (n + 1) * (b / c);
  long long m = (a * n + b) / c;
  return n * m - f(m - 1, c, c - b - 1, a);
}
long long exgcd(long long a, long long b, long long &x, long long &y) {
  if (!b) return x = 1, y = 0, a;
  long long t = exgcd(b, a % b, y, x);
  y -= a / b * x;
  return t;
}
void solve() {
  scanf("%d%d%d%d", &a, &b, &p, &q);
  long long l = 0, r = q, mid, res, P = p * 2ll, Q = q * 2ll, L, R;
  while (l <= r) {
    mid = (l + r) >> 1, L = q - mid, R = q + mid + 1;
    if (f(b, P, Q - L, Q) - f(a - 1, P, Q - L, Q) + f(a - 1, P, Q - R, Q) -
            f(b, P, Q - R, Q) >
        0)
      r = mid - 1, res = mid;
    else
      l = mid + 1;
  }
  long long x, y, g = exgcd(P, Q, x, y), ans = 2e9;
  P /= g, Q /= g;
  if ((q - res) % g == 0) {
    long long xx = (q - res) / g * x;
    xx += (a - xx) / Q * Q;
    while (xx >= a) xx -= Q;
    while (xx < a) xx += Q;
    ans = min(ans, xx);
  }
  if ((q + res) % g == 0) {
    long long xx = (q + res) / g * x;
    xx += (a - xx) / Q * Q;
    while (xx >= a) xx -= Q;
    while (xx < a) xx += Q;
    ans = min(ans, xx);
  }
  printf("%lld\n", ans);
}
int main() {
  scanf("%d", &T);
  while (T--) solve();
}

### Prompt

Develop a solution in cpp to the problem described below:

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;
int T, a, b, p, q;
long long f(long long n, long long a, long long b, long long c) {
  if (!a) return b / c * (n + 1);
  if (a >= c || b >= c)
    return f(n, a % c, b % c, c) + n * (n + 1) / 2 * (a / c) +
           (n + 1) * (b / c);
  long long m = (a * n + b) / c;
  return n * m - f(m - 1, c, c - b - 1, a);
}
long long exgcd(long long a, long long b, long long &x, long long &y) {
  if (!b) return x = 1, y = 0, a;
  long long t = exgcd(b, a % b, y, x);
  y -= a / b * x;
  return t;
}
void solve() {
  scanf("%d%d%d%d", &a, &b, &p, &q);
  long long l = 0, r = q, mid, res, P = p * 2ll, Q = q * 2ll, L, R;
  while (l <= r) {
    mid = (l + r) >> 1, L = q - mid, R = q + mid + 1;
    if (f(b, P, Q - L, Q) - f(a - 1, P, Q - L, Q) + f(a - 1, P, Q - R, Q) -
            f(b, P, Q - R, Q) >
        0)
      r = mid - 1, res = mid;
    else
      l = mid + 1;
  }
  long long x, y, g = exgcd(P, Q, x, y), ans = 2e9;
  P /= g, Q /= g;
  if ((q - res) % g == 0) {
    long long xx = (q - res) / g * x;
    xx += (a - xx) / Q * Q;
    while (xx >= a) xx -= Q;
    while (xx < a) xx += Q;
    ans = min(ans, xx);
  }
  if ((q + res) % g == 0) {
    long long xx = (q + res) / g * x;
    xx += (a - xx) / Q * Q;
    while (xx >= a) xx -= Q;
    while (xx < a) xx += Q;
    ans = min(ans, xx);
  }
  printf("%lld\n", ans);
}
int main() {
  scanf("%d", &T);
  while (T--) solve();
}

```