#include <bits/stdc++.h>
using namespace std;
long long eucli(long long n, long long a, long long b, long long c) {
  if (n < 0) return 0;
  if (n == 0) return b / c;
  if (b < 0) return eucli(n, a, b + c, c) - (n + 1);
  if (a >= c || b >= c)
    return eucli(n, a % c, b % c, c) + (a / c * n * (n + 1) / 2) +
           (b / c * (n + 1));
  long long m = (a * n + b) / c;
  return n * m - eucli(m - 1, c, c - b - 1, a);
}
long long eucli(long long l, long long r, long long a, long long b,
                long long c) {
  return eucli(r, a, b, c) - eucli(l - 1, a, b, c);
}
long long exgcd(long long a, long long b, long long &x, long long &y) {
  if (!b) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = exgcd(b, a % b, x, y);
  long long temp = x;
  x = y;
  y = temp - (a / b) * y;
  return d;
}
long long solve(long long p, long long q, long long mod, long long l,
                long long r) {
  const long long Inf = 1e18;
  long long x, y;
  long long gcd = exgcd(p, q, x, y);
  if (mod % gcd != 0) return Inf;
  p /= gcd;
  q /= gcd;
  mod /= gcd;
  x *= mod;
  y *= mod;
  x += ((l - x) / q) * q;
  if (x < l) x += q;
  return x;
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    long long a, b, p, q;
    scanf("%I64d %I64d %I64d %I64d", &a, &b, &p, &q);
    p = p % q;
    long long left = 0;
    long long right = q;
    long long mid, l, r;
    while (left < right) {
      mid = (left + right) / 2;
      l = q - mid;
      r = q + mid;
      if (eucli(a, b, 2 * p, -l, 2 * q) - eucli(a, b, 2 * p, -r - 1, 2 * q) >
          0) {
        right = mid;
      } else
        left = mid + 1;
    }
    long long mod = q - left;
    long long ans = solve(2 * p, 2 * q, mod, a, b);
    mod = q + left;
    long long new_ans = solve(2 * p, 2 * q, mod, a, b);
    if (ans > new_ans) ans = new_ans;
    if (q == 1) ans = a;
    printf("%I64d\n", 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;
long long eucli(long long n, long long a, long long b, long long c) {
  if (n < 0) return 0;
  if (n == 0) return b / c;
  if (b < 0) return eucli(n, a, b + c, c) - (n + 1);
  if (a >= c || b >= c)
    return eucli(n, a % c, b % c, c) + (a / c * n * (n + 1) / 2) +
           (b / c * (n + 1));
  long long m = (a * n + b) / c;
  return n * m - eucli(m - 1, c, c - b - 1, a);
}
long long eucli(long long l, long long r, long long a, long long b,
                long long c) {
  return eucli(r, a, b, c) - eucli(l - 1, a, b, c);
}
long long exgcd(long long a, long long b, long long &x, long long &y) {
  if (!b) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = exgcd(b, a % b, x, y);
  long long temp = x;
  x = y;
  y = temp - (a / b) * y;
  return d;
}
long long solve(long long p, long long q, long long mod, long long l,
                long long r) {
  const long long Inf = 1e18;
  long long x, y;
  long long gcd = exgcd(p, q, x, y);
  if (mod % gcd != 0) return Inf;
  p /= gcd;
  q /= gcd;
  mod /= gcd;
  x *= mod;
  y *= mod;
  x += ((l - x) / q) * q;
  if (x < l) x += q;
  return x;
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    long long a, b, p, q;
    scanf("%I64d %I64d %I64d %I64d", &a, &b, &p, &q);
    p = p % q;
    long long left = 0;
    long long right = q;
    long long mid, l, r;
    while (left < right) {
      mid = (left + right) / 2;
      l = q - mid;
      r = q + mid;
      if (eucli(a, b, 2 * p, -l, 2 * q) - eucli(a, b, 2 * p, -r - 1, 2 * q) >
          0) {
        right = mid;
      } else
        left = mid + 1;
    }
    long long mod = q - left;
    long long ans = solve(2 * p, 2 * q, mod, a, b);
    mod = q + left;
    long long new_ans = solve(2 * p, 2 * q, mod, a, b);
    if (ans > new_ans) ans = new_ans;
    if (q == 1) ans = a;
    printf("%I64d\n", ans);
  }
}

```