#include <bits/stdc++.h>
using namespace std;
long long f(long long a, long long b, long long c, long long n);
long long g(long long a, long long b, long long c, long long n);
long long h(long long a, long long b, long long c, long long n);
struct query {
  long long f, g, h;
};
inline long long read() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
inline void print(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) print(x / 10);
  putchar(x % 10 + '0');
}
query solve(long long a, long long b, long long c, long long n) {
  query ans, tmp;
  if (a == 0) {
    ans.f = (n + 1) * (b / c);
    ans.g = (b / c) * n * (n + 1) / 2;
    ans.h = (n + 1) * (b / c) * (b / c);
    return ans;
  }
  if (a >= c || b >= c) {
    tmp = solve(a % c, b % c, c, n);
    ans.f = tmp.f + (a / c) * n * (n + 1) / 2 + (b / c) * (n + 1);
    ans.g = tmp.g + (a / c) * n * (n + 1) * (2 * n + 1) / 6 +
            (b / c) * n * (n + 1) / 2;
    ans.h = (a / c) * (a / c) * n * (n + 1) * (2 * n + 1) / 6 +
            (b / c) * (b / c) * (n + 1) + (a / c) * (b / c) * n * (n + 1) +
            tmp.h + 2 * (a / c) * tmp.g + 2 * (b / c) * tmp.f;
    return ans;
  }
  long long m = (a * n + b) / c;
  tmp = solve(c, c - b - 1, a, m - 1);
  ans.f = (n * m - tmp.f);
  ans.g = (n * (n + 1) * m - tmp.f - tmp.h) / 2;
  ans.h = (n * m * (m + 1) - 2 * tmp.g - 2 * tmp.f - ans.f);
  return ans;
}
long long exgcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  int gcd = exgcd(b, a % b, x, y), t = x;
  x = y, y = t - a / b * y;
  return gcd;
}
void dec(long long &tmp, long long left, long long round) {
  while (tmp >= left) tmp -= round;
  while (tmp < left) tmp += round;
}
long long a, b, p, q, t;
long long ans = 1e18;
int main() {
  t = read();
  while (t--) {
    a = read(), b = read(), p = read(), q = read();
    long long x = 0, y = 0, l = 0, r = q, pp = p << 1, qq = q << 1;
    ans = 1e18;
    while (l < r) {
      long long mid = (l + r) >> 1;
      query solve1 = solve(pp, qq - (q - mid), qq, b);
      query solve2 = solve(pp, qq - (q + mid + 1), qq, a - 1);
      query solve3 = solve(pp, qq - (q - mid), qq, a - 1);
      query solve4 = solve(pp, qq - (q + mid + 1), qq, b);
      long long tmp = solve1.f + solve2.f - solve3.f - solve4.f;
      tmp > 0 ? r = mid : l = mid + 1;
    }
    long long gcd = exgcd(pp, qq, x, y);
    pp /= gcd;
    qq /= gcd;
    if ((q - l) % gcd == 0) {
      long long tmp = (q - l) / gcd * x;
      tmp += (a - tmp) / qq * qq;
      dec(tmp, a, qq);
      ans = min(ans, tmp);
    }
    if ((q + l) % gcd == 0) {
      long long tmp = (q + l) / gcd * x;
      tmp += (a - tmp) / qq * qq;
      dec(tmp, a, qq);
      ans = min(ans, tmp);
    }
    print(ans);
    puts("");
  }
  return 0;
}

### Prompt

Generate 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 f(long long a, long long b, long long c, long long n);
long long g(long long a, long long b, long long c, long long n);
long long h(long long a, long long b, long long c, long long n);
struct query {
  long long f, g, h;
};
inline long long read() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
inline void print(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) print(x / 10);
  putchar(x % 10 + '0');
}
query solve(long long a, long long b, long long c, long long n) {
  query ans, tmp;
  if (a == 0) {
    ans.f = (n + 1) * (b / c);
    ans.g = (b / c) * n * (n + 1) / 2;
    ans.h = (n + 1) * (b / c) * (b / c);
    return ans;
  }
  if (a >= c || b >= c) {
    tmp = solve(a % c, b % c, c, n);
    ans.f = tmp.f + (a / c) * n * (n + 1) / 2 + (b / c) * (n + 1);
    ans.g = tmp.g + (a / c) * n * (n + 1) * (2 * n + 1) / 6 +
            (b / c) * n * (n + 1) / 2;
    ans.h = (a / c) * (a / c) * n * (n + 1) * (2 * n + 1) / 6 +
            (b / c) * (b / c) * (n + 1) + (a / c) * (b / c) * n * (n + 1) +
            tmp.h + 2 * (a / c) * tmp.g + 2 * (b / c) * tmp.f;
    return ans;
  }
  long long m = (a * n + b) / c;
  tmp = solve(c, c - b - 1, a, m - 1);
  ans.f = (n * m - tmp.f);
  ans.g = (n * (n + 1) * m - tmp.f - tmp.h) / 2;
  ans.h = (n * m * (m + 1) - 2 * tmp.g - 2 * tmp.f - ans.f);
  return ans;
}
long long exgcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  int gcd = exgcd(b, a % b, x, y), t = x;
  x = y, y = t - a / b * y;
  return gcd;
}
void dec(long long &tmp, long long left, long long round) {
  while (tmp >= left) tmp -= round;
  while (tmp < left) tmp += round;
}
long long a, b, p, q, t;
long long ans = 1e18;
int main() {
  t = read();
  while (t--) {
    a = read(), b = read(), p = read(), q = read();
    long long x = 0, y = 0, l = 0, r = q, pp = p << 1, qq = q << 1;
    ans = 1e18;
    while (l < r) {
      long long mid = (l + r) >> 1;
      query solve1 = solve(pp, qq - (q - mid), qq, b);
      query solve2 = solve(pp, qq - (q + mid + 1), qq, a - 1);
      query solve3 = solve(pp, qq - (q - mid), qq, a - 1);
      query solve4 = solve(pp, qq - (q + mid + 1), qq, b);
      long long tmp = solve1.f + solve2.f - solve3.f - solve4.f;
      tmp > 0 ? r = mid : l = mid + 1;
    }
    long long gcd = exgcd(pp, qq, x, y);
    pp /= gcd;
    qq /= gcd;
    if ((q - l) % gcd == 0) {
      long long tmp = (q - l) / gcd * x;
      tmp += (a - tmp) / qq * qq;
      dec(tmp, a, qq);
      ans = min(ans, tmp);
    }
    if ((q + l) % gcd == 0) {
      long long tmp = (q + l) / gcd * x;
      tmp += (a - tmp) / qq * qq;
      dec(tmp, a, qq);
      ans = min(ans, tmp);
    }
    print(ans);
    puts("");
  }
  return 0;
}

```