#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
int a, b, p, q;
int tst;
const int A = sqrt((int)1e9);
pair<int, int> best;
void upd(int x) {
  int val = abs(2 * ((1LL * p * x) % q) - q);
  best = min(best, make_pair(val, x));
}
void solve() {
  cin >> a >> b >> p >> q;
  best = make_pair(q + 1000, -1);
  while (b % A != (A - 1)) {
    upd(b);
    b--;
    if (b < a) break;
  }
  while (a % A != 0) {
    upd(a);
    a++;
    if (b < a) break;
  }
  if (b < a) {
    cout << best.second << '\n';
    return;
  }
  int l = a / A;
  int r = b / A;
  vector<pair<unsigned int, int> > f1, f2;
  for (int i = l; i <= r; i++) {
    f1.push_back(make_pair((1LL * p * A * i) % q, i));
  }
  for (int i = 0; i < A; i++) {
    f2.push_back(make_pair((1LL * p * i) % q, i));
  }
  sort(f1.begin(), f1.end());
  vector<pair<unsigned int, int> > nf1, nf2;
  for (int i = 0; i < f1.size(); i++) {
    if (i > 0 && f1[i].first == f1[i - 1].first) continue;
    nf1.push_back(f1[i]);
  }
  f1 = nf1;
  sort(f2.begin(), f2.end());
  for (int i = 0; i < f2.size(); i++) {
    if (i > 0 && f2[i].first == f2[i - 1].first) continue;
    nf2.push_back(f2[i]);
  }
  f2 = nf2;
  int ri = 0;
  unsigned int qq = q;
  reverse(f1.begin(), f1.end());
  for (int i = 0; i < f1.size(); i++) {
    while (ri < f2.size() && 2 * (f1[i].first + f2[ri].first) < qq) ri++;
    ri--;
    ri = max(ri, 0);
    for (int j = ri; j <= ri + 1; j++) {
      if (j >= 0 && j < f2.size()) {
        upd(f1[i].second * A + f2[j].second);
      }
    }
  }
  ri = 0;
  for (int i = 0; i < f1.size(); i++) {
    while (ri < f2.size() && (2 * (f1[i].first + f2[ri].first)) < 3 * qq) {
      ri++;
    }
    ri--;
    ri = max(ri, 0);
    for (int j = ri; j <= ri + 1; j++) {
      if (j >= 0 && j < f2.size()) {
        upd(f1[i].second * A + f2[j].second);
      }
    }
  }
  cout << best.second << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> tst;
  while (tst--) {
    solve();
  }
  return 0;
}

### Prompt

Your task is to create 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>
#pragma GCC optimize("O3")
using namespace std;
int a, b, p, q;
int tst;
const int A = sqrt((int)1e9);
pair<int, int> best;
void upd(int x) {
  int val = abs(2 * ((1LL * p * x) % q) - q);
  best = min(best, make_pair(val, x));
}
void solve() {
  cin >> a >> b >> p >> q;
  best = make_pair(q + 1000, -1);
  while (b % A != (A - 1)) {
    upd(b);
    b--;
    if (b < a) break;
  }
  while (a % A != 0) {
    upd(a);
    a++;
    if (b < a) break;
  }
  if (b < a) {
    cout << best.second << '\n';
    return;
  }
  int l = a / A;
  int r = b / A;
  vector<pair<unsigned int, int> > f1, f2;
  for (int i = l; i <= r; i++) {
    f1.push_back(make_pair((1LL * p * A * i) % q, i));
  }
  for (int i = 0; i < A; i++) {
    f2.push_back(make_pair((1LL * p * i) % q, i));
  }
  sort(f1.begin(), f1.end());
  vector<pair<unsigned int, int> > nf1, nf2;
  for (int i = 0; i < f1.size(); i++) {
    if (i > 0 && f1[i].first == f1[i - 1].first) continue;
    nf1.push_back(f1[i]);
  }
  f1 = nf1;
  sort(f2.begin(), f2.end());
  for (int i = 0; i < f2.size(); i++) {
    if (i > 0 && f2[i].first == f2[i - 1].first) continue;
    nf2.push_back(f2[i]);
  }
  f2 = nf2;
  int ri = 0;
  unsigned int qq = q;
  reverse(f1.begin(), f1.end());
  for (int i = 0; i < f1.size(); i++) {
    while (ri < f2.size() && 2 * (f1[i].first + f2[ri].first) < qq) ri++;
    ri--;
    ri = max(ri, 0);
    for (int j = ri; j <= ri + 1; j++) {
      if (j >= 0 && j < f2.size()) {
        upd(f1[i].second * A + f2[j].second);
      }
    }
  }
  ri = 0;
  for (int i = 0; i < f1.size(); i++) {
    while (ri < f2.size() && (2 * (f1[i].first + f2[ri].first)) < 3 * qq) {
      ri++;
    }
    ri--;
    ri = max(ri, 0);
    for (int j = ri; j <= ri + 1; j++) {
      if (j >= 0 && j < f2.size()) {
        upd(f1[i].second * A + f2[j].second);
      }
    }
  }
  cout << best.second << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> tst;
  while (tst--) {
    solve();
  }
  return 0;
}

```