#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("fast-math")
#pragma comment(linker, "/STACK:256000000")
#pragma warning(disable : 4996)
using namespace std;
const char el = '\n';
const int inf = 1e9;
const long long llinf = 1e18, mod = 998244353, md = 998244352;
const long double pi =
    3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825;
template <typename T>
bool uin(T &a, T b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename T>
bool uax(T &a, T b) {
  if (b > a) {
    a = b;
    return 1;
  }
  return 0;
}
template <class iterator>
void output(iterator begin, iterator end, char p = ' ', ostream &out = cout) {
  while (begin != end) {
    out << (*begin) << p;
    begin++;
  }
  out << el;
}
template <class T>
void output(T first, char p = ' ', ostream &out = cout) {
  output(first.begin(), first.end(), p, out);
}
mt19937 rnd(time(NULL));
long long gcd(long long a, long long b) {
  while (b > 0) {
    a %= b;
    swap(a, b);
  }
  return a;
}
long long gcdex(long long a, long long b, long long &first, long long &second) {
  if (a == 0) {
    first = 0;
    second = 1;
    return b;
  }
  long long x1, y1;
  long long d = gcdex(b % a, a, x1, y1);
  first = y1 - (b / a) * x1;
  second = x1;
  return d;
}
const long long T1 = 100000, T2 = 100000;
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long t;
  cin >> t;
  while (t--) {
    long long a, b, p, q;
    cin >> a >> b >> p >> q;
    pair<long long, long long> ans(inf, inf);
    long long k = gcd(p, q);
    p /= k;
    q /= k;
    long long w = 0;
    if (b - a >= q) b = a + q - 1;
    if (b - a <= T1) {
      for (long long first = a; first <= b; ++first) {
        long long tmp = first * p % q;
        if (tmp < 0) tmp += q;
        uin(ans, {max(tmp, q - tmp), first});
      }
    } else {
      w = (a / q) * q;
      a %= q;
      b %= q;
      if (a < 0) a += q;
      if (b < 0) b += q;
      long long tmp = a * p % q;
      if (tmp < 0) tmp += q;
      uin(ans, {max(tmp, q - tmp), a});
      tmp = b * p % q;
      if (tmp < 0) tmp += q;
      uin(ans, {max(tmp, q - tmp), b >= a ? b : b + q});
      long long first, second;
      gcdex(p, q, first, second);
      first = (first % q + q) % q;
      long long lt = max(0ll, (q - T2) / 2), rt = min(q - 1, (q + T2) / 2);
      for (long long i = lt; i <= rt; ++i) {
        long long j = i * first % q;
        if (j < 0) j += q;
        if ((a <= j && j <= b) || (a > b && !(b < j && j < a)))
          uin(ans, {max(i, q - i), j >= a ? j : j + q});
      }
    }
    cout << ans.second + w << el;
  }
  return 0;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("fast-math")
#pragma comment(linker, "/STACK:256000000")
#pragma warning(disable : 4996)
using namespace std;
const char el = '\n';
const int inf = 1e9;
const long long llinf = 1e18, mod = 998244353, md = 998244352;
const long double pi =
    3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825;
template <typename T>
bool uin(T &a, T b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename T>
bool uax(T &a, T b) {
  if (b > a) {
    a = b;
    return 1;
  }
  return 0;
}
template <class iterator>
void output(iterator begin, iterator end, char p = ' ', ostream &out = cout) {
  while (begin != end) {
    out << (*begin) << p;
    begin++;
  }
  out << el;
}
template <class T>
void output(T first, char p = ' ', ostream &out = cout) {
  output(first.begin(), first.end(), p, out);
}
mt19937 rnd(time(NULL));
long long gcd(long long a, long long b) {
  while (b > 0) {
    a %= b;
    swap(a, b);
  }
  return a;
}
long long gcdex(long long a, long long b, long long &first, long long &second) {
  if (a == 0) {
    first = 0;
    second = 1;
    return b;
  }
  long long x1, y1;
  long long d = gcdex(b % a, a, x1, y1);
  first = y1 - (b / a) * x1;
  second = x1;
  return d;
}
const long long T1 = 100000, T2 = 100000;
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long t;
  cin >> t;
  while (t--) {
    long long a, b, p, q;
    cin >> a >> b >> p >> q;
    pair<long long, long long> ans(inf, inf);
    long long k = gcd(p, q);
    p /= k;
    q /= k;
    long long w = 0;
    if (b - a >= q) b = a + q - 1;
    if (b - a <= T1) {
      for (long long first = a; first <= b; ++first) {
        long long tmp = first * p % q;
        if (tmp < 0) tmp += q;
        uin(ans, {max(tmp, q - tmp), first});
      }
    } else {
      w = (a / q) * q;
      a %= q;
      b %= q;
      if (a < 0) a += q;
      if (b < 0) b += q;
      long long tmp = a * p % q;
      if (tmp < 0) tmp += q;
      uin(ans, {max(tmp, q - tmp), a});
      tmp = b * p % q;
      if (tmp < 0) tmp += q;
      uin(ans, {max(tmp, q - tmp), b >= a ? b : b + q});
      long long first, second;
      gcdex(p, q, first, second);
      first = (first % q + q) % q;
      long long lt = max(0ll, (q - T2) / 2), rt = min(q - 1, (q + T2) / 2);
      for (long long i = lt; i <= rt; ++i) {
        long long j = i * first % q;
        if (j < 0) j += q;
        if ((a <= j && j <= b) || (a > b && !(b < j && j < a)))
          uin(ans, {max(i, q - i), j >= a ? j : j + q});
      }
    }
    cout << ans.second + w << el;
  }
  return 0;
}

```