#include <bits/stdc++.h>
using namespace std;
int T, a, b, p, q;
map<int, bool> m;
int cnt = 0;
pair<int, int> e[200001];
int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%d %d %d %d", &a, &b, &p, &q);
    int t = (int)sqrt((b - a + 1) * 1.) + 1;
    m.clear();
    cnt = 0;
    pair<int, int> mn = make_pair(0x3f3f3f3f, 0x3f3f3f3f);
    for (int i = 0; i < t; i++) {
      int tmp = 2LL * (i + a) * p % (2 * q);
      if (!m.count(tmp)) {
        e[++cnt] = make_pair(tmp, i);
        m[tmp] = true;
      }
    }
    sort(e + 1, e + 1 + cnt);
    int cur = q, st;
    for (int i = 0; i <= 1000000; i++) {
      if ((i + 1) * t - 1 + a > b) {
        st = a + i * t;
        break;
      }
      int l = 1, r = cnt;
      while (l <= r) {
        int mid = (l + r) >> 1;
        if (e[mid].first <= cur)
          l = mid + 1;
        else
          r = mid - 1;
      }
      pair<int, int> tmpans;
      if (r == 0) {
        tmpans = make_pair(e[l].first - cur, e[l].second + i * t + a);
        tmpans = min(tmpans, make_pair(cur + 2 * q - e[cnt].first,
                                       e[cnt].second + i * t + a));
      } else if (r == cnt) {
        tmpans = make_pair(cur - e[r].first, e[r].second + i * t + a);
        tmpans = min(tmpans, make_pair(2 * q - cur + e[1].first,
                                       e[1].second + i * t + a));
      } else
        tmpans = min(make_pair(cur - e[r].first, e[r].second + i * t + a),
                     make_pair(e[l].first - cur, e[l].second + i * t + a));
      mn = min(mn, tmpans);
      if (mn.first == 5) {
        ++i;
        --i;
      }
      cur = (cur - 2LL * p * t % (2 * q) + 2 * q) % (2 * q);
    }
    for (int i = st; i <= b; i++) {
      int tmp = 2LL * i * p % (2 * q);
      tmp = abs(tmp - q);
      pair<int, int> ts = make_pair(tmp, i);
      mn = min(mn, ts);
    }
    printf("%d\n", mn.second);
  }
  return 0;
}

### Prompt

In cpp, your task is to solve 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>
using namespace std;
int T, a, b, p, q;
map<int, bool> m;
int cnt = 0;
pair<int, int> e[200001];
int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%d %d %d %d", &a, &b, &p, &q);
    int t = (int)sqrt((b - a + 1) * 1.) + 1;
    m.clear();
    cnt = 0;
    pair<int, int> mn = make_pair(0x3f3f3f3f, 0x3f3f3f3f);
    for (int i = 0; i < t; i++) {
      int tmp = 2LL * (i + a) * p % (2 * q);
      if (!m.count(tmp)) {
        e[++cnt] = make_pair(tmp, i);
        m[tmp] = true;
      }
    }
    sort(e + 1, e + 1 + cnt);
    int cur = q, st;
    for (int i = 0; i <= 1000000; i++) {
      if ((i + 1) * t - 1 + a > b) {
        st = a + i * t;
        break;
      }
      int l = 1, r = cnt;
      while (l <= r) {
        int mid = (l + r) >> 1;
        if (e[mid].first <= cur)
          l = mid + 1;
        else
          r = mid - 1;
      }
      pair<int, int> tmpans;
      if (r == 0) {
        tmpans = make_pair(e[l].first - cur, e[l].second + i * t + a);
        tmpans = min(tmpans, make_pair(cur + 2 * q - e[cnt].first,
                                       e[cnt].second + i * t + a));
      } else if (r == cnt) {
        tmpans = make_pair(cur - e[r].first, e[r].second + i * t + a);
        tmpans = min(tmpans, make_pair(2 * q - cur + e[1].first,
                                       e[1].second + i * t + a));
      } else
        tmpans = min(make_pair(cur - e[r].first, e[r].second + i * t + a),
                     make_pair(e[l].first - cur, e[l].second + i * t + a));
      mn = min(mn, tmpans);
      if (mn.first == 5) {
        ++i;
        --i;
      }
      cur = (cur - 2LL * p * t % (2 * q) + 2 * q) % (2 * q);
    }
    for (int i = st; i <= b; i++) {
      int tmp = 2LL * i * p % (2 * q);
      tmp = abs(tmp - q);
      pair<int, int> ts = make_pair(tmp, i);
      mn = min(mn, ts);
    }
    printf("%d\n", mn.second);
  }
  return 0;
}

```