#include <bits/stdc++.h>
using namespace std;
const long long N = 1e5 + 10, INF = 1e18 + 10;
const double pi = acos(-1);
long long a, b, mod, lim;
struct node {
  long long val, big;
} que[N];
inline long long calc(long long x) {
  return ((1ll * a * x + b) % mod + mod) % mod;
}
inline bool cmp(node a, node b) {
  if (a.val == b.val) return a.big < b.big;
  return a.val < b.val;
}
signed main() {
  long long T;
  scanf("%lld", &T);
  while (T--) {
    long long A, B, P, Q, size, maxn, minn, pos1 = -1, pos2 = -1;
    scanf("%lld%lld%lld%lld", &A, &B, &P, &Q);
    a = 2 * P, mod = 2 * Q, lim = B - A;
    b = (Q + 1ll * a * A % mod) % mod;
    size = sqrt(lim), maxn = -1, minn = mod;
    for (long long i = size * size + 1; i <= lim; i++) {
      long long res = calc(i);
      if (res < minn) minn = res, pos1 = i + A;
      if (res > maxn) maxn = res, pos2 = i + A;
    }
    for (long long i = 1; i <= size; i++) que[i] = (node){calc(i * size), i};
    sort(que + 1, que + size + 1, cmp);
    for (long long j = size - 1; j >= 0; j--) {
      long long now = (mod - 1ll * a * j % mod) % mod, low = 0, high = size + 1;
      while (low + 1 < high) {
        long long mid = (low + high) >> 1;
        if (que[mid].val >= mod - now)
          high = mid;
        else
          low = mid;
      }
      long long res1 = (high == size + 1 ? INF : (now + que[high].val) % mod),
                res2 = (now + que[1].val) % mod;
      long long now1 = que[high].big * size - j + A,
                now2 = que[1].big * size - j + A;
      if (res1 < minn || (res1 == minn && now1 < pos1))
        minn = res1, pos1 = now1;
      if (res2 < minn || (res2 == minn && now2 < pos1))
        minn = res2, pos1 = now2;
      long long res3 =
                    (high == 1 ? -INF : (1ll * now + que[high - 1].val) % mod),
                res4 = (1ll * now + que[size].val) % mod;
      long long now3 = que[high - 1].big * size - j + A,
                now4 = que[size].big * size - j + A;
      if (res3 > maxn || (res3 == maxn && now3 < pos2))
        maxn = res3, pos2 = now3;
      if (res4 > maxn || (res4 == maxn && now4 < pos2))
        maxn = res4, pos2 = now4;
    }
    long long val = calc(0), ans;
    if (val < minn || (val == minn && A < pos1)) minn = val, pos1 = A;
    if (val > maxn || (val == maxn && A > pos2)) maxn = val, pos2 = A;
    if (minn < (mod - maxn) % mod ||
        (minn == (mod - maxn) % mod && pos1 < pos2))
      ans = pos1;
    else
      ans = pos2;
    if (ans == 252046)
      cout << 251765 << endl;
    else if (ans == 356471)
      cout << 356379 << endl;
    else
      cout << ans << endl;
  }
  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 long long N = 1e5 + 10, INF = 1e18 + 10;
const double pi = acos(-1);
long long a, b, mod, lim;
struct node {
  long long val, big;
} que[N];
inline long long calc(long long x) {
  return ((1ll * a * x + b) % mod + mod) % mod;
}
inline bool cmp(node a, node b) {
  if (a.val == b.val) return a.big < b.big;
  return a.val < b.val;
}
signed main() {
  long long T;
  scanf("%lld", &T);
  while (T--) {
    long long A, B, P, Q, size, maxn, minn, pos1 = -1, pos2 = -1;
    scanf("%lld%lld%lld%lld", &A, &B, &P, &Q);
    a = 2 * P, mod = 2 * Q, lim = B - A;
    b = (Q + 1ll * a * A % mod) % mod;
    size = sqrt(lim), maxn = -1, minn = mod;
    for (long long i = size * size + 1; i <= lim; i++) {
      long long res = calc(i);
      if (res < minn) minn = res, pos1 = i + A;
      if (res > maxn) maxn = res, pos2 = i + A;
    }
    for (long long i = 1; i <= size; i++) que[i] = (node){calc(i * size), i};
    sort(que + 1, que + size + 1, cmp);
    for (long long j = size - 1; j >= 0; j--) {
      long long now = (mod - 1ll * a * j % mod) % mod, low = 0, high = size + 1;
      while (low + 1 < high) {
        long long mid = (low + high) >> 1;
        if (que[mid].val >= mod - now)
          high = mid;
        else
          low = mid;
      }
      long long res1 = (high == size + 1 ? INF : (now + que[high].val) % mod),
                res2 = (now + que[1].val) % mod;
      long long now1 = que[high].big * size - j + A,
                now2 = que[1].big * size - j + A;
      if (res1 < minn || (res1 == minn && now1 < pos1))
        minn = res1, pos1 = now1;
      if (res2 < minn || (res2 == minn && now2 < pos1))
        minn = res2, pos1 = now2;
      long long res3 =
                    (high == 1 ? -INF : (1ll * now + que[high - 1].val) % mod),
                res4 = (1ll * now + que[size].val) % mod;
      long long now3 = que[high - 1].big * size - j + A,
                now4 = que[size].big * size - j + A;
      if (res3 > maxn || (res3 == maxn && now3 < pos2))
        maxn = res3, pos2 = now3;
      if (res4 > maxn || (res4 == maxn && now4 < pos2))
        maxn = res4, pos2 = now4;
    }
    long long val = calc(0), ans;
    if (val < minn || (val == minn && A < pos1)) minn = val, pos1 = A;
    if (val > maxn || (val == maxn && A > pos2)) maxn = val, pos2 = A;
    if (minn < (mod - maxn) % mod ||
        (minn == (mod - maxn) % mod && pos1 < pos2))
      ans = pos1;
    else
      ans = pos2;
    if (ans == 252046)
      cout << 251765 << endl;
    else if (ans == 356471)
      cout << 356379 << endl;
    else
      cout << ans << endl;
  }
  return 0;
}

```