#include <bits/stdc++.h>
using namespace std;
const int inf_int = 1e9 + 100;
const long long inf_ll = 1e18;
const double pi = 3.1415926535898;
bool debug = 0;
const int MAXN = 1e6 + 100;
const int LOG = 21;
const int mod = 1e9 + 7;
const int MX = (1e7 + 100) * 1.5;
const long long MOD = 1000000000949747713ll;
template <class T1, class T2>
std::ostream &operator<<(std::ostream &out, const std::pair<T1, T2> &rhs) {
  out << "( " << rhs.first << " , " << rhs.second << " )";
  return out;
}
inline long long dist(long long &a, long long &b, long long q) {
  long long val = abs(b - a);
  if (val > q) val = 2 * q - val;
  return val;
}
void solve() {
  long long a, b, p, q;
  cin >> a >> b >> p >> q;
  if (abs(b - a) <= 10) {
    long long ans = inf_ll;
    long long pos = -1;
    for (long long x = a; x <= b; ++x) {
      long long ret = (2 * p * x) % (2 * q);
      ret = dist(ret, q, q);
      if (ret < ans) {
        ans = ret;
        pos = x;
      }
    }
    cout << pos << "\n";
    return;
  }
  long long block = sqrt(b - a);
  vector<pair<long long, long long> > vals;
  for (int x = a; x < a + block; ++x) {
    long long ret = (2 * p * x) % (2 * q);
    vals.push_back({ret, x});
  }
  sort(vals.begin(), vals.end());
  vector<pair<long long, long long> > good;
  for (int i = 0; i < (int(vals.size())); ++i) {
    if (i > 0 && vals[i].first == vals[i - 1].first) continue;
    good.push_back(vals[i]);
    if (debug) cout << vals[i].first << " " << vals[i].second << endl;
  }
  long long ans = inf_ll;
  long long pos = -1;
  long long mod = 2 * q;
  long long last = a;
  for (long long a0 = a; a0 + block - 1 <= b; a0 += block) {
    long long add = (a0 - a) * (2 * p);
    long long dif = a0 - a;
    add = add % mod;
    long long need = (q - add + mod) % mod;
    if (debug) cout << "here " << a0 << " " << add << " -- " << need << endl;
    pair<long long, long long> temp = {need, -1};
    int i = lower_bound(good.begin(), good.end(), temp) - good.begin();
    if (i < (int(good.size()))) {
      int ps = i;
      if (dist(good[ps].first, need, q) < ans) {
        ans = dist(good[ps].first, need, q);
        pos = good[ps].second + dif;
      } else if (dist(good[ps].first, need, q) == ans &&
                 good[ps].second + dif < pos) {
        pos = good[ps].second + dif;
      }
    }
    if (i > 0) {
      int ps = i - 1;
      if (dist(good[ps].first, need, q) < ans) {
        ans = dist(good[ps].first, need, q);
        pos = good[ps].second + dif;
      } else if (dist(good[ps].first, need, q) == ans &&
                 good[ps].second + dif < pos) {
        pos = good[ps].second + dif;
      }
    }
    {
      int ps = 0;
      if (dist(good[ps].first, need, q) < ans) {
        ans = dist(good[ps].first, need, q);
        pos = good[ps].second + dif;
      } else if (dist(good[ps].first, need, q) == ans &&
                 good[ps].second + dif < pos) {
        pos = good[ps].second + dif;
      }
      ps = (int(good.size())) - 1;
      if (dist(good[ps].first, need, q) < ans) {
        ans = dist(good[ps].first, need, q);
        pos = good[ps].second + dif;
      } else if (dist(good[ps].first, need, q) == ans &&
                 good[ps].second + dif < pos) {
        pos = good[ps].second + dif;
      }
    }
    if (debug) cout << "!! " << ans << " " << pos << endl;
    last = a0 + block - 1;
  }
  if (debug) cout << "last " << last << endl;
  for (long long x = last + 1; x <= b; ++x) {
    long long ret = (2 * p * x) % mod;
    ret = abs(ret - q);
    if (ret < ans) {
      ans = ret;
      pos = x;
    }
  }
  cout << pos << "\n";
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout.setf(ios::fixed);
  cout.precision(20);
  int t = 1;
  cin >> t;
  while (t--) solve();
  if (debug)
    cerr << endl << "time : " << (1.0 * clock() / CLOCKS_PER_SEC) << endl;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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;
const int inf_int = 1e9 + 100;
const long long inf_ll = 1e18;
const double pi = 3.1415926535898;
bool debug = 0;
const int MAXN = 1e6 + 100;
const int LOG = 21;
const int mod = 1e9 + 7;
const int MX = (1e7 + 100) * 1.5;
const long long MOD = 1000000000949747713ll;
template <class T1, class T2>
std::ostream &operator<<(std::ostream &out, const std::pair<T1, T2> &rhs) {
  out << "( " << rhs.first << " , " << rhs.second << " )";
  return out;
}
inline long long dist(long long &a, long long &b, long long q) {
  long long val = abs(b - a);
  if (val > q) val = 2 * q - val;
  return val;
}
void solve() {
  long long a, b, p, q;
  cin >> a >> b >> p >> q;
  if (abs(b - a) <= 10) {
    long long ans = inf_ll;
    long long pos = -1;
    for (long long x = a; x <= b; ++x) {
      long long ret = (2 * p * x) % (2 * q);
      ret = dist(ret, q, q);
      if (ret < ans) {
        ans = ret;
        pos = x;
      }
    }
    cout << pos << "\n";
    return;
  }
  long long block = sqrt(b - a);
  vector<pair<long long, long long> > vals;
  for (int x = a; x < a + block; ++x) {
    long long ret = (2 * p * x) % (2 * q);
    vals.push_back({ret, x});
  }
  sort(vals.begin(), vals.end());
  vector<pair<long long, long long> > good;
  for (int i = 0; i < (int(vals.size())); ++i) {
    if (i > 0 && vals[i].first == vals[i - 1].first) continue;
    good.push_back(vals[i]);
    if (debug) cout << vals[i].first << " " << vals[i].second << endl;
  }
  long long ans = inf_ll;
  long long pos = -1;
  long long mod = 2 * q;
  long long last = a;
  for (long long a0 = a; a0 + block - 1 <= b; a0 += block) {
    long long add = (a0 - a) * (2 * p);
    long long dif = a0 - a;
    add = add % mod;
    long long need = (q - add + mod) % mod;
    if (debug) cout << "here " << a0 << " " << add << " -- " << need << endl;
    pair<long long, long long> temp = {need, -1};
    int i = lower_bound(good.begin(), good.end(), temp) - good.begin();
    if (i < (int(good.size()))) {
      int ps = i;
      if (dist(good[ps].first, need, q) < ans) {
        ans = dist(good[ps].first, need, q);
        pos = good[ps].second + dif;
      } else if (dist(good[ps].first, need, q) == ans &&
                 good[ps].second + dif < pos) {
        pos = good[ps].second + dif;
      }
    }
    if (i > 0) {
      int ps = i - 1;
      if (dist(good[ps].first, need, q) < ans) {
        ans = dist(good[ps].first, need, q);
        pos = good[ps].second + dif;
      } else if (dist(good[ps].first, need, q) == ans &&
                 good[ps].second + dif < pos) {
        pos = good[ps].second + dif;
      }
    }
    {
      int ps = 0;
      if (dist(good[ps].first, need, q) < ans) {
        ans = dist(good[ps].first, need, q);
        pos = good[ps].second + dif;
      } else if (dist(good[ps].first, need, q) == ans &&
                 good[ps].second + dif < pos) {
        pos = good[ps].second + dif;
      }
      ps = (int(good.size())) - 1;
      if (dist(good[ps].first, need, q) < ans) {
        ans = dist(good[ps].first, need, q);
        pos = good[ps].second + dif;
      } else if (dist(good[ps].first, need, q) == ans &&
                 good[ps].second + dif < pos) {
        pos = good[ps].second + dif;
      }
    }
    if (debug) cout << "!! " << ans << " " << pos << endl;
    last = a0 + block - 1;
  }
  if (debug) cout << "last " << last << endl;
  for (long long x = last + 1; x <= b; ++x) {
    long long ret = (2 * p * x) % mod;
    ret = abs(ret - q);
    if (ret < ans) {
      ans = ret;
      pos = x;
    }
  }
  cout << pos << "\n";
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout.setf(ios::fixed);
  cout.precision(20);
  int t = 1;
  cin >> t;
  while (t--) solve();
  if (debug)
    cerr << endl << "time : " << (1.0 * clock() / CLOCKS_PER_SEC) << endl;
}

```