#include <bits/stdc++.h>
using namespace std;
void file(string s) {
  freopen((s + ".in").c_str(), "r", stdin);
  freopen((s + ".out").c_str(), "w", stdout);
}
template <typename Tp>
void read(Tp &x) {
  long long fh = 1;
  char c = getchar();
  x = 0;
  while (c > '9' || c < '0') {
    if (c == '-') {
      fh = -1;
    }
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = (x << 1) + (x << 3) + (c & 15);
    c = getchar();
  }
  x *= fh;
}
long long n, m;
long long S1(long long x) { return x * (x - 1) / 2; }
long long getf(long long n, long long a, long long b, long long c) {
  if (n <= 0) return 0;
  if (n == 0) return b / c;
  if (a >= c || b >= c)
    return (a / c) * S1(n) + (b / c) * n + getf(n, a % c, b % c, c);
  else {
    if (a == 0) return (b / c) * n;
    long long tm = (a * n + b) / c;
    return tm * (n - 1) - getf(tm, c, c - b - 1, a);
  }
}
long long getf_(long long n, long long a, long long b, long long c) {
  if (b >= 0) return getf(n, a, b, c);
  long long bb = (b % c + c) % c;
  long long dlt = (bb - b) / c;
  return getf(n, a, bb, c) - n * dlt;
}
long long p, q, A, B;
bool chk(long long g) {
  long long L = q - g, R = q + g;
  long long sm1 = getf_(B + 1, 2 * p, -L, 2 * q) - getf_(A, 2 * p, -L, 2 * q);
  long long sm2 =
      getf_(B + 1, 2 * p, -R - 1, 2 * q) - getf_(A, 2 * p, -R - 1, 2 * q);
  return sm1 > sm2;
}
long long gcd(long long x, long long y) { return y ? gcd(y, x % y) : x; }
void exgcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1, y = 0;
    return;
  }
  exgcd(b, a % b, y, x);
  y -= (a / b) * x;
}
long long calc(long long c) {
  long long a = 2 * p, b = 2 * q;
  long long g = gcd(a, b);
  if (c % g) return 0x3f3f3f3f3f3f3f3fll;
  a /= g;
  b /= g;
  c /= g;
  long long x, y;
  exgcd(a, b, x, y);
  x = x * c;
  x = (x % b + b) % b;
  long long tms = floor((A - 1 - x) * 1.0 / b);
  x += (tms + 1) * b;
  if (x <= B)
    return x;
  else
    return 0x3f3f3f3f3f3f3f3fll;
}
signed main() {
  long long CasT;
  read(CasT);
  while (CasT--) {
    read(A);
    read(B);
    read(p);
    read(q);
    long long l = 0, r = q;
    while (l < r) {
      long long mid = ((l + r) >> 1);
      if (chk(mid))
        r = mid;
      else
        l = mid + 1;
    }
    long long ans1 = calc(q + l), ans2 = calc(q - l);
    printf("%lld\n", min(ans1, ans2));
  }
  return 0;
}

### Prompt

In cpp, your task is to solve 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;
void file(string s) {
  freopen((s + ".in").c_str(), "r", stdin);
  freopen((s + ".out").c_str(), "w", stdout);
}
template <typename Tp>
void read(Tp &x) {
  long long fh = 1;
  char c = getchar();
  x = 0;
  while (c > '9' || c < '0') {
    if (c == '-') {
      fh = -1;
    }
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = (x << 1) + (x << 3) + (c & 15);
    c = getchar();
  }
  x *= fh;
}
long long n, m;
long long S1(long long x) { return x * (x - 1) / 2; }
long long getf(long long n, long long a, long long b, long long c) {
  if (n <= 0) return 0;
  if (n == 0) return b / c;
  if (a >= c || b >= c)
    return (a / c) * S1(n) + (b / c) * n + getf(n, a % c, b % c, c);
  else {
    if (a == 0) return (b / c) * n;
    long long tm = (a * n + b) / c;
    return tm * (n - 1) - getf(tm, c, c - b - 1, a);
  }
}
long long getf_(long long n, long long a, long long b, long long c) {
  if (b >= 0) return getf(n, a, b, c);
  long long bb = (b % c + c) % c;
  long long dlt = (bb - b) / c;
  return getf(n, a, bb, c) - n * dlt;
}
long long p, q, A, B;
bool chk(long long g) {
  long long L = q - g, R = q + g;
  long long sm1 = getf_(B + 1, 2 * p, -L, 2 * q) - getf_(A, 2 * p, -L, 2 * q);
  long long sm2 =
      getf_(B + 1, 2 * p, -R - 1, 2 * q) - getf_(A, 2 * p, -R - 1, 2 * q);
  return sm1 > sm2;
}
long long gcd(long long x, long long y) { return y ? gcd(y, x % y) : x; }
void exgcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1, y = 0;
    return;
  }
  exgcd(b, a % b, y, x);
  y -= (a / b) * x;
}
long long calc(long long c) {
  long long a = 2 * p, b = 2 * q;
  long long g = gcd(a, b);
  if (c % g) return 0x3f3f3f3f3f3f3f3fll;
  a /= g;
  b /= g;
  c /= g;
  long long x, y;
  exgcd(a, b, x, y);
  x = x * c;
  x = (x % b + b) % b;
  long long tms = floor((A - 1 - x) * 1.0 / b);
  x += (tms + 1) * b;
  if (x <= B)
    return x;
  else
    return 0x3f3f3f3f3f3f3f3fll;
}
signed main() {
  long long CasT;
  read(CasT);
  while (CasT--) {
    read(A);
    read(B);
    read(p);
    read(q);
    long long l = 0, r = q;
    while (l < r) {
      long long mid = ((l + r) >> 1);
      if (chk(mid))
        r = mid;
      else
        l = mid + 1;
    }
    long long ans1 = calc(q + l), ans2 = calc(q - l);
    printf("%lld\n", min(ans1, ans2));
  }
  return 0;
}

```