#include <bits/stdc++.h>
using namespace std;
long long get_arith(long long a, long long b, long long c, long long N) {
  long long res = (a / c) * N * (N - 1) / 2 + (b / c) * N;
  a %= c;
  b %= c;
  if (a) res += get_arith(c, (a * N + b) % c, a, (a * N + b) / c);
  return res;
}
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
pair<long long, long long> Exgcd(long long a, long long b) {
  if (a == 0) return {0, 1};
  if (b == 0) return {1, 0};
  long long q = a / b;
  pair<long long, long long> t = Exgcd(b, a % b);
  return pair<long long, long long>(t.second, t.first - t.second * q);
}
long long Get2(long long p, long long q, long long pv) {
  while (pv < 0) pv += q;
  long long g = gcd(p, q);
  p /= g, q /= g, pv /= g;
  pair<long long, long long> tp = Exgcd(p, q);
  long long inv = (tp.first % q + q) % q;
  return inv * pv % q;
}
long long Min(long long be, long long p, long long q, long long c) {
  be += q;
  p %= q;
  if (p == 0) return 0;
  long long M = get_arith(p, be, q, c);
  long long bb = 0, ee = q, mid, res = q + 1, pv = 1e18;
  long long pv1, pv2, res1, res2;
  while (bb <= ee) {
    mid = (bb + ee) >> 1;
    long long z = get_arith(p, be + mid, q, c);
    if (z == M)
      bb = mid + 1;
    else {
      res = min(res, mid);
      pv = -be - mid;
      ee = mid - 1;
    }
  }
  pv1 = pv;
  res1 = res;
  bb = 0, ee = q;
  res = q + 1;
  while (bb <= ee) {
    mid = (bb + ee) >> 1;
    long long z = get_arith(p, be - mid, q, c);
    if (z == M)
      bb = mid + 1;
    else {
      if (res > mid - 1) {
        res = mid - 1;
        pv = mid - 1 - be;
      }
      ee = mid - 1;
    }
  }
  res2 = res;
  pv2 = pv;
  if (pv > 7e17) return 0;
  if (res1 == res2) {
    long long t1 = Get2(p, q, pv1);
    long long t2 = Get2(p, q, pv2);
    return min(t1, t2);
  } else if (res1 < res2) {
    return Get2(p, q, pv1);
  } else {
    return Get2(p, q, pv2);
  }
}
int main() {
  long long a, b, p, q, TC;
  scanf("%lld", &TC);
  while (TC--) {
    scanf("%lld%lld%lld%lld", &a, &b, &p, &q);
    long long be = (a * (2 * p) + q) % (2 * q);
    long long res = a + Min(be, 2 * p, 2 * q, b - a + 1);
    printf("%lld\n", res);
  }
}

### Prompt

Please formulate 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>
using namespace std;
long long get_arith(long long a, long long b, long long c, long long N) {
  long long res = (a / c) * N * (N - 1) / 2 + (b / c) * N;
  a %= c;
  b %= c;
  if (a) res += get_arith(c, (a * N + b) % c, a, (a * N + b) / c);
  return res;
}
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
pair<long long, long long> Exgcd(long long a, long long b) {
  if (a == 0) return {0, 1};
  if (b == 0) return {1, 0};
  long long q = a / b;
  pair<long long, long long> t = Exgcd(b, a % b);
  return pair<long long, long long>(t.second, t.first - t.second * q);
}
long long Get2(long long p, long long q, long long pv) {
  while (pv < 0) pv += q;
  long long g = gcd(p, q);
  p /= g, q /= g, pv /= g;
  pair<long long, long long> tp = Exgcd(p, q);
  long long inv = (tp.first % q + q) % q;
  return inv * pv % q;
}
long long Min(long long be, long long p, long long q, long long c) {
  be += q;
  p %= q;
  if (p == 0) return 0;
  long long M = get_arith(p, be, q, c);
  long long bb = 0, ee = q, mid, res = q + 1, pv = 1e18;
  long long pv1, pv2, res1, res2;
  while (bb <= ee) {
    mid = (bb + ee) >> 1;
    long long z = get_arith(p, be + mid, q, c);
    if (z == M)
      bb = mid + 1;
    else {
      res = min(res, mid);
      pv = -be - mid;
      ee = mid - 1;
    }
  }
  pv1 = pv;
  res1 = res;
  bb = 0, ee = q;
  res = q + 1;
  while (bb <= ee) {
    mid = (bb + ee) >> 1;
    long long z = get_arith(p, be - mid, q, c);
    if (z == M)
      bb = mid + 1;
    else {
      if (res > mid - 1) {
        res = mid - 1;
        pv = mid - 1 - be;
      }
      ee = mid - 1;
    }
  }
  res2 = res;
  pv2 = pv;
  if (pv > 7e17) return 0;
  if (res1 == res2) {
    long long t1 = Get2(p, q, pv1);
    long long t2 = Get2(p, q, pv2);
    return min(t1, t2);
  } else if (res1 < res2) {
    return Get2(p, q, pv1);
  } else {
    return Get2(p, q, pv2);
  }
}
int main() {
  long long a, b, p, q, TC;
  scanf("%lld", &TC);
  while (TC--) {
    scanf("%lld%lld%lld%lld", &a, &b, &p, &q);
    long long be = (a * (2 * p) + q) % (2 * q);
    long long res = a + Min(be, 2 * p, 2 * q, b - a + 1);
    printf("%lld\n", res);
  }
}

```