#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long T, A, B, P, Q;
long long n, i, j, k;
long long ans;
pair<long long, long long> rec(long long p, long long q, long long r,
                               long long e, long long e2, long long n) {
  if (n < r / p * e) {
    return {r - n / e * p, n - n / e * e};
  }
  if (r % p == 0) {
    return {0, n - r / p * e};
  }
  if (q % p == 0) {
    return {r - r / p * p, n - r / p * e};
  }
  pair<long long, long long> anss =
      rec(p - q % p, p, r - r / p * p, e * (q / p + 1) - e2, e, n - r / p * e);
  return anss;
}
inline void query() {
  scanf("%lld%lld%lld%lld", &A, &B, &P, &Q);
  if (P % Q == 0) {
    printf("%lld\n", A);
    return;
  }
  long long st = A * P % Q;
  long long l = 0, r = Q / 2;
  pair<long long, long long> aaa, bbb;
  while (l < r) {
    long long m = (l + r) / 2;
    if (Q - P % Q > P % Q) {
      aaa = rec(P % Q, Q, (Q / 2 + Q % 2 - st + Q + m) % Q, 1, 0, B - A);
    } else {
      aaa = rec(Q - P % Q, Q, (st - Q / 2 + Q + m) % Q, 1, 0, B - A);
    }
    if (aaa.first <= m * 2 + Q % 2) {
      r = m;
    } else {
      l = m + 1;
    }
  }
  aaa = {1, 1};
  bbb = {1, 1};
  if (Q - P % Q > P % Q) {
    aaa = rec(P % Q, Q, (Q / 2 + Q % 2 - st + Q + r) % Q, 1, 0, B - A);
    if ((Q / 2 - st + Q) % Q >= r)
      bbb = rec(P % Q, Q, (Q / 2 - st + Q) % Q - r, 1, 0, B - A);
  } else {
    aaa = rec(Q - P % Q, Q, (st - Q / 2 + Q + r) % Q, 1, 0, B - A);
    if ((st - Q / 2 - Q % 2 + Q) % Q >= r)
      bbb = rec(Q - P % Q, Q, (st - Q / 2 - Q % 2 + Q) % Q - r, 1, 0, B - A);
  }
  if (aaa.first == 0 || bbb.first == 0) {
    if (bbb.first == 0) {
      if (aaa.first == 0) {
        if (bbb.second > aaa.second) aaa = bbb;
      } else {
        aaa = bbb;
      }
    }
    printf("%lld\n", B - aaa.second);
    return;
  }
}
int main() {
  long long T;
  scanf("%lld", &T);
  while (T--) query();
}

### 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) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long T, A, B, P, Q;
long long n, i, j, k;
long long ans;
pair<long long, long long> rec(long long p, long long q, long long r,
                               long long e, long long e2, long long n) {
  if (n < r / p * e) {
    return {r - n / e * p, n - n / e * e};
  }
  if (r % p == 0) {
    return {0, n - r / p * e};
  }
  if (q % p == 0) {
    return {r - r / p * p, n - r / p * e};
  }
  pair<long long, long long> anss =
      rec(p - q % p, p, r - r / p * p, e * (q / p + 1) - e2, e, n - r / p * e);
  return anss;
}
inline void query() {
  scanf("%lld%lld%lld%lld", &A, &B, &P, &Q);
  if (P % Q == 0) {
    printf("%lld\n", A);
    return;
  }
  long long st = A * P % Q;
  long long l = 0, r = Q / 2;
  pair<long long, long long> aaa, bbb;
  while (l < r) {
    long long m = (l + r) / 2;
    if (Q - P % Q > P % Q) {
      aaa = rec(P % Q, Q, (Q / 2 + Q % 2 - st + Q + m) % Q, 1, 0, B - A);
    } else {
      aaa = rec(Q - P % Q, Q, (st - Q / 2 + Q + m) % Q, 1, 0, B - A);
    }
    if (aaa.first <= m * 2 + Q % 2) {
      r = m;
    } else {
      l = m + 1;
    }
  }
  aaa = {1, 1};
  bbb = {1, 1};
  if (Q - P % Q > P % Q) {
    aaa = rec(P % Q, Q, (Q / 2 + Q % 2 - st + Q + r) % Q, 1, 0, B - A);
    if ((Q / 2 - st + Q) % Q >= r)
      bbb = rec(P % Q, Q, (Q / 2 - st + Q) % Q - r, 1, 0, B - A);
  } else {
    aaa = rec(Q - P % Q, Q, (st - Q / 2 + Q + r) % Q, 1, 0, B - A);
    if ((st - Q / 2 - Q % 2 + Q) % Q >= r)
      bbb = rec(Q - P % Q, Q, (st - Q / 2 - Q % 2 + Q) % Q - r, 1, 0, B - A);
  }
  if (aaa.first == 0 || bbb.first == 0) {
    if (bbb.first == 0) {
      if (aaa.first == 0) {
        if (bbb.second > aaa.second) aaa = bbb;
      } else {
        aaa = bbb;
      }
    }
    printf("%lld\n", B - aaa.second);
    return;
  }
}
int main() {
  long long T;
  scanf("%lld", &T);
  while (T--) query();
}

```