#include <bits/stdc++.h>
using namespace std;
const int SQRT = 180000;
const long long INF = (long long)1e18 + 5;
long long a, b, p, q;
long long tab[SQRT], ans, dist, mod;
int sz;
pair<int, int> inp[SQRT];
void update(long long pos, long long val) {
  if (val == dist) {
    ans = min(ans, pos);
  } else if (val < dist) {
    ans = pos;
    dist = val;
  }
}
void test(long long id) {
  long long add = 2 * p * id % mod * SQRT % mod;
  int head = lower_bound(tab, tab + sz, (mod - add) % mod) - tab;
  if (head == sz) head = 0;
  long long l = 0, r = sz - 1, res = head;
  while (l <= r) {
    long long m = (l + r) >> 1, pos = (head + m) % sz,
              val = (tab[pos] + add) % mod;
    if (val >= q) {
      r = m - 1;
      res = pos;
    } else {
      l = m + 1;
    }
  }
  update(inp[res].second + id * SQRT, abs(q - (tab[res] + add) % mod));
  l = 0, r = sz - 1, res = (head - 1 + mod) % mod;
  while (l <= r) {
    long long m = (l + r) >> 1, pos = (head + m) % sz,
              val = (tab[pos] + add) % mod;
    if (val > q) {
      r = m - 1;
    } else {
      l = m + 1;
      res = pos;
    }
  }
  update(inp[res].second + id * SQRT, abs(q - (tab[res] + add) % mod));
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int T;
  cin >> T;
  while (T--) {
    cin >> a >> b >> p >> q;
    mod = 2 * q;
    ans = INF;
    dist = INF;
    for (int i = 0; i < SQRT; i++) {
      inp[i] = {2 * p * i % mod, i};
    }
    sort(inp, inp + SQRT);
    sz = 0;
    int ptr = 0;
    while (ptr < SQRT) {
      inp[sz++] = inp[ptr];
      int r = ptr + 1;
      while (r < SQRT && inp[r].first == inp[ptr].first) r++;
      ptr = r;
    }
    for (int i = 0; i < sz; i++) {
      tab[i] = inp[i].first;
    }
    long long lb = a / SQRT, rb = b / SQRT;
    for (int i = a; i <= min(b, (lb + 1) * SQRT); i++) {
      int res = abs(2 * p * i % mod - q);
      if (res < dist) {
        dist = res;
        ans = i;
      }
    }
    for (int i = lb + 1; i < rb; i++) {
      test(i);
    }
    for (int i = max(a, rb * SQRT); i <= b; i++) {
      int res = abs(2 * p * i % mod - q);
      if (res < dist) {
        dist = res;
        ans = i;
      }
    }
    cout << ans << '\n';
  }
  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>
using namespace std;
const int SQRT = 180000;
const long long INF = (long long)1e18 + 5;
long long a, b, p, q;
long long tab[SQRT], ans, dist, mod;
int sz;
pair<int, int> inp[SQRT];
void update(long long pos, long long val) {
  if (val == dist) {
    ans = min(ans, pos);
  } else if (val < dist) {
    ans = pos;
    dist = val;
  }
}
void test(long long id) {
  long long add = 2 * p * id % mod * SQRT % mod;
  int head = lower_bound(tab, tab + sz, (mod - add) % mod) - tab;
  if (head == sz) head = 0;
  long long l = 0, r = sz - 1, res = head;
  while (l <= r) {
    long long m = (l + r) >> 1, pos = (head + m) % sz,
              val = (tab[pos] + add) % mod;
    if (val >= q) {
      r = m - 1;
      res = pos;
    } else {
      l = m + 1;
    }
  }
  update(inp[res].second + id * SQRT, abs(q - (tab[res] + add) % mod));
  l = 0, r = sz - 1, res = (head - 1 + mod) % mod;
  while (l <= r) {
    long long m = (l + r) >> 1, pos = (head + m) % sz,
              val = (tab[pos] + add) % mod;
    if (val > q) {
      r = m - 1;
    } else {
      l = m + 1;
      res = pos;
    }
  }
  update(inp[res].second + id * SQRT, abs(q - (tab[res] + add) % mod));
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int T;
  cin >> T;
  while (T--) {
    cin >> a >> b >> p >> q;
    mod = 2 * q;
    ans = INF;
    dist = INF;
    for (int i = 0; i < SQRT; i++) {
      inp[i] = {2 * p * i % mod, i};
    }
    sort(inp, inp + SQRT);
    sz = 0;
    int ptr = 0;
    while (ptr < SQRT) {
      inp[sz++] = inp[ptr];
      int r = ptr + 1;
      while (r < SQRT && inp[r].first == inp[ptr].first) r++;
      ptr = r;
    }
    for (int i = 0; i < sz; i++) {
      tab[i] = inp[i].first;
    }
    long long lb = a / SQRT, rb = b / SQRT;
    for (int i = a; i <= min(b, (lb + 1) * SQRT); i++) {
      int res = abs(2 * p * i % mod - q);
      if (res < dist) {
        dist = res;
        ans = i;
      }
    }
    for (int i = lb + 1; i < rb; i++) {
      test(i);
    }
    for (int i = max(a, rb * SQRT); i <= b; i++) {
      int res = abs(2 * p * i % mod - q);
      if (res < dist) {
        dist = res;
        ans = i;
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

```