#include <bits/stdc++.h>
using namespace std;
int T, a, b, p, q;
long long calc(long long n, long long a, long long b, long long c) {
  if (a == 0)
    return 1LL * (n + 1) * (b / c);
  else if (b >= c) {
    long long res = 1LL * (n + 1) * (b / c);
    res += calc(n, a, b % c, c);
    return res;
  } else if (a >= c) {
    long long res = (1LL * (n + 1) * n * (a / c)) / 2;
    res += calc(n, a % c, b, c);
    return res;
  } else {
    long long res = 1LL * n * ((1LL * a * n + b) / c);
    res -= calc((1LL * a * n + b) / c - 1, c, c - b - 1, a);
    return res;
  }
}
bool check(int now, int a, int b) {
  if (now == q) return true;
  long long cnt = 0LL;
  cnt += calc(b, 2 * p, q + now, 2 * q) - calc(b, 2 * p, q - now - 1, 2 * q);
  cnt -= calc(a - 1, 2 * p, q + now, 2 * q) -
         calc(a - 1, 2 * p, q - now - 1, 2 * q);
  return cnt > 0LL;
}
int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d%d%d", &a, &b, &p, &q);
    int lx = 0, rx = q;
    while (rx - lx > 1) {
      int mid = (lx + rx) / 2;
      if (check(mid, a, b))
        rx = mid;
      else
        lx = mid;
    }
    int now;
    if (check(lx, a, b))
      now = lx;
    else
      now = rx;
    lx = a, rx = b;
    while (rx - lx > 1) {
      int mid = (lx + rx) / 2;
      if (check(now, a, mid))
        rx = mid;
      else
        lx = mid;
    }
    if (check(now, a, lx))
      printf("%d\n", lx);
    else
      printf("%d\n", rx);
  }
  return 0;
}

### Prompt

Please formulate 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;
int T, a, b, p, q;
long long calc(long long n, long long a, long long b, long long c) {
  if (a == 0)
    return 1LL * (n + 1) * (b / c);
  else if (b >= c) {
    long long res = 1LL * (n + 1) * (b / c);
    res += calc(n, a, b % c, c);
    return res;
  } else if (a >= c) {
    long long res = (1LL * (n + 1) * n * (a / c)) / 2;
    res += calc(n, a % c, b, c);
    return res;
  } else {
    long long res = 1LL * n * ((1LL * a * n + b) / c);
    res -= calc((1LL * a * n + b) / c - 1, c, c - b - 1, a);
    return res;
  }
}
bool check(int now, int a, int b) {
  if (now == q) return true;
  long long cnt = 0LL;
  cnt += calc(b, 2 * p, q + now, 2 * q) - calc(b, 2 * p, q - now - 1, 2 * q);
  cnt -= calc(a - 1, 2 * p, q + now, 2 * q) -
         calc(a - 1, 2 * p, q - now - 1, 2 * q);
  return cnt > 0LL;
}
int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d%d%d", &a, &b, &p, &q);
    int lx = 0, rx = q;
    while (rx - lx > 1) {
      int mid = (lx + rx) / 2;
      if (check(mid, a, b))
        rx = mid;
      else
        lx = mid;
    }
    int now;
    if (check(lx, a, b))
      now = lx;
    else
      now = rx;
    lx = a, rx = b;
    while (rx - lx > 1) {
      int mid = (lx + rx) / 2;
      if (check(now, a, mid))
        rx = mid;
      else
        lx = mid;
    }
    if (check(now, a, lx))
      printf("%d\n", lx);
    else
      printf("%d\n", rx);
  }
  return 0;
}

```