#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const long long LL_INF = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
inline void cmin(int &x, int y) {
  if (y < x) x = y;
}
inline void cmax(int &x, int y) {
  if (y > x) x = y;
}
const int B = 30000;
pair<int, int> tmp[B];
int id[B], val[B];
int C = 0;
void init(long long p, long long q) {
  for (int i = 0; i < B; i++) tmp[i] = {p * i % q, i};
  sort(tmp, tmp + B);
  C = 0;
  for (int i = 0; i < B; i++) {
    if (i == 0 || tmp[i].first != tmp[i - 1].first) {
      val[C] = tmp[i].first;
      id[C] = tmp[i].second;
      C++;
    }
  }
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    long long a, b, p, q;
    cin >> a >> b >> p >> q;
    p %= q;
    p *= 2;
    q *= 2;
    init(p, q);
    long long x = a, cur = p * a % q;
    long long best = INF, ans = -1;
    while (x + B <= b) {
      int pos;
      if (cur <= q / 2)
        pos = lower_bound(val, val + C, q / 2 - cur) - val;
      else
        pos = lower_bound(val, val + C, 3 * q / 2 - cur) - val;
      if (pos >= 1) {
        long long v = cur + val[pos - 1];
        if (v >= q) {
          v -= q;
        }
        if (abs(q / 2 - v) < best ||
            abs(q / 2 - v) == best && x + id[pos - 1] < ans) {
          best = abs(q / 2 - v);
          ans = x + id[pos - 1];
        }
      }
      if (pos < C) {
        long long v = cur + val[pos];
        if (v >= q) {
          v -= q;
        }
        if (abs(q / 2 - v) < best ||
            abs(q / 2 - v) == best && x + id[pos] < ans) {
          best = abs(q / 2 - v);
          ans = x + id[pos];
        }
      }
      cur = (cur + B * p) % q;
      x += B;
    }
    while (x <= b) {
      if (abs(q / 2 - cur) < best) {
        best = abs(q / 2 - cur);
        ans = x;
      }
      cur += p;
      if (cur >= q) cur -= q;
      x++;
    }
    cout << ans << "\n";
  }
  return 0;
}

### 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 MOD = 1e9 + 7;
const long long LL_INF = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
inline void cmin(int &x, int y) {
  if (y < x) x = y;
}
inline void cmax(int &x, int y) {
  if (y > x) x = y;
}
const int B = 30000;
pair<int, int> tmp[B];
int id[B], val[B];
int C = 0;
void init(long long p, long long q) {
  for (int i = 0; i < B; i++) tmp[i] = {p * i % q, i};
  sort(tmp, tmp + B);
  C = 0;
  for (int i = 0; i < B; i++) {
    if (i == 0 || tmp[i].first != tmp[i - 1].first) {
      val[C] = tmp[i].first;
      id[C] = tmp[i].second;
      C++;
    }
  }
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    long long a, b, p, q;
    cin >> a >> b >> p >> q;
    p %= q;
    p *= 2;
    q *= 2;
    init(p, q);
    long long x = a, cur = p * a % q;
    long long best = INF, ans = -1;
    while (x + B <= b) {
      int pos;
      if (cur <= q / 2)
        pos = lower_bound(val, val + C, q / 2 - cur) - val;
      else
        pos = lower_bound(val, val + C, 3 * q / 2 - cur) - val;
      if (pos >= 1) {
        long long v = cur + val[pos - 1];
        if (v >= q) {
          v -= q;
        }
        if (abs(q / 2 - v) < best ||
            abs(q / 2 - v) == best && x + id[pos - 1] < ans) {
          best = abs(q / 2 - v);
          ans = x + id[pos - 1];
        }
      }
      if (pos < C) {
        long long v = cur + val[pos];
        if (v >= q) {
          v -= q;
        }
        if (abs(q / 2 - v) < best ||
            abs(q / 2 - v) == best && x + id[pos] < ans) {
          best = abs(q / 2 - v);
          ans = x + id[pos];
        }
      }
      cur = (cur + B * p) % q;
      x += B;
    }
    while (x <= b) {
      if (abs(q / 2 - cur) < best) {
        best = abs(q / 2 - cur);
        ans = x;
      }
      cur += p;
      if (cur >= q) cur -= q;
      x++;
    }
    cout << ans << "\n";
  }
  return 0;
}

```