#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  bool flag = false;
  while (!isdigit(c)) {
    if (c == '-') flag = true;
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + (c ^ 48);
    c = getchar();
  }
  if (flag) x = -x;
}
int T;
long long a, b, p, q, l, r, ans;
long long f(long long n, long long a, long long b, long long c) {
  if (n < 0) return 0;
  if (!a) return (n + 1) * (b / c);
  if (a >= c || b >= c)
    return (n + 1) * n / 2 * (a / c) + (n + 1) * (b / c) +
           f(n, a % c, b % c, c);
  long long m = (n * a + b) / c;
  return n * m - f(m - 1, c, c - b - 1, a);
}
bool check(long long v) {
  long long l = q / 2 - v, r = q / 2 + v, v1, v2;
  return f(b, p, q - l, q) - f(a - 1, p, q - l, q) - f(b, p, q - r - 1, q) +
         f(a - 1, p, q - r - 1, q);
}
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
void exgcd(long long a, long long b, long long &x, long long &y) {
  if (!b)
    x = 1, y = 0;
  else
    exgcd(b, a % b, y, x), y -= a / b * x;
}
long long calc(long long p, long long q, long long a, long long b,
               long long v) {
  long long g = gcd(p, q), x, y;
  if (v % g) return 1000000000000000000;
  p /= g, q /= g, exgcd(p, q, x, y);
  x *= v / g, x += (a - x) / q * q;
  while (x < a) x += q;
  while (x - q >= a) x -= q;
  if (x > b) return 1000000000000000000;
}
int main() {
  read(T);
  while (T--) {
    read(a), read(b), read(p), read(q), l = ans = 0, r = q, p *= 2, q *= 2;
    while (l <= r) {
      long long mid = (l + r) >> 1;
      if (check(mid))
        ans = mid, r = mid - 1;
      else
        l = mid + 1;
    }
    printf("%lld\n",
           min(calc(p, q, a, b, q / 2 - ans), calc(p, q, a, b, q / 2 + ans)));
  }
  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;
template <typename T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  bool flag = false;
  while (!isdigit(c)) {
    if (c == '-') flag = true;
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + (c ^ 48);
    c = getchar();
  }
  if (flag) x = -x;
}
int T;
long long a, b, p, q, l, r, ans;
long long f(long long n, long long a, long long b, long long c) {
  if (n < 0) return 0;
  if (!a) return (n + 1) * (b / c);
  if (a >= c || b >= c)
    return (n + 1) * n / 2 * (a / c) + (n + 1) * (b / c) +
           f(n, a % c, b % c, c);
  long long m = (n * a + b) / c;
  return n * m - f(m - 1, c, c - b - 1, a);
}
bool check(long long v) {
  long long l = q / 2 - v, r = q / 2 + v, v1, v2;
  return f(b, p, q - l, q) - f(a - 1, p, q - l, q) - f(b, p, q - r - 1, q) +
         f(a - 1, p, q - r - 1, q);
}
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
void exgcd(long long a, long long b, long long &x, long long &y) {
  if (!b)
    x = 1, y = 0;
  else
    exgcd(b, a % b, y, x), y -= a / b * x;
}
long long calc(long long p, long long q, long long a, long long b,
               long long v) {
  long long g = gcd(p, q), x, y;
  if (v % g) return 1000000000000000000;
  p /= g, q /= g, exgcd(p, q, x, y);
  x *= v / g, x += (a - x) / q * q;
  while (x < a) x += q;
  while (x - q >= a) x -= q;
  if (x > b) return 1000000000000000000;
}
int main() {
  read(T);
  while (T--) {
    read(a), read(b), read(p), read(q), l = ans = 0, r = q, p *= 2, q *= 2;
    while (l <= r) {
      long long mid = (l + r) >> 1;
      if (check(mid))
        ans = mid, r = mid - 1;
      else
        l = mid + 1;
    }
    printf("%lld\n",
           min(calc(p, q, a, b, q / 2 - ans), calc(p, q, a, b, q / 2 + ans)));
  }
  return 0;
}

```