#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + (ch ^ 48);
    ch = getchar();
  }
  return x * f;
}
const long long N = 114514;
long long a, b, c, p, q, k, l, r, x, y, z, w, ans;
inline long long s(long long x) { return x * (x + 1) / 2; }
inline long long f(long long a, long long b, long long c, long long n) {
  if (!a || !n) return b / c * (n + 1);
  if (n < 0) return 0;
  if (a >= c || b >= c)
    return f(a % c, b % c, c, n) + (a / c) * s(n) + (b / c) * (n + 1);
  long long k = (a * n + b) / c;
  return n * k - f(c, c - b - 1, a, k - 1);
}
inline long long exgcd(long long a, long long b, long long &x, long long &y) {
  if (!b) {
    x = 1;
    y = 0;
    return a;
  }
  long long ans = exgcd(b, a % b, y, x);
  y -= a / b * x;
  return ans;
}
inline void mian() {
  a = read();
  b = read();
  p = read();
  q = read();
  l = 0;
  r = q;
  x = p << 1;
  y = q << 1;
  while (l < r) {
    long long mid = l + r >> 1;
    z = q - mid;
    w = q + mid + 1;
    if (f(x, y - z, y, b) + f(x, y - w, y, a - 1) - f(x, y - z, y, a - 1) -
            f(x, y - w, y, b) >
        0)
      r = mid;
    else
      l = mid + 1;
  }
  k = exgcd(x, y, z, w);
  ans = 1000000000;
  x /= k;
  y /= k;
  if ((q - l) % k == 0) {
    c = (q - l) / k * z;
    c += (a - c) / y * y;
    while (c >= a) c -= y;
    while (c < a) c += y;
    ans = min(ans, c);
  }
  if ((q + l) % k == 0) {
    c = (q + l) / k * z;
    c += (a - c) / y * y;
    while (c >= a) c -= y;
    while (c < a) c += y;
    ans = min(ans, c);
  }
  printf("%lld\n", ans);
}
signed main() {
  long long qwq = read();
  while (qwq--) mian();
  return 0;
}

### Prompt

Your task is to create 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;
inline long long read() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + (ch ^ 48);
    ch = getchar();
  }
  return x * f;
}
const long long N = 114514;
long long a, b, c, p, q, k, l, r, x, y, z, w, ans;
inline long long s(long long x) { return x * (x + 1) / 2; }
inline long long f(long long a, long long b, long long c, long long n) {
  if (!a || !n) return b / c * (n + 1);
  if (n < 0) return 0;
  if (a >= c || b >= c)
    return f(a % c, b % c, c, n) + (a / c) * s(n) + (b / c) * (n + 1);
  long long k = (a * n + b) / c;
  return n * k - f(c, c - b - 1, a, k - 1);
}
inline long long exgcd(long long a, long long b, long long &x, long long &y) {
  if (!b) {
    x = 1;
    y = 0;
    return a;
  }
  long long ans = exgcd(b, a % b, y, x);
  y -= a / b * x;
  return ans;
}
inline void mian() {
  a = read();
  b = read();
  p = read();
  q = read();
  l = 0;
  r = q;
  x = p << 1;
  y = q << 1;
  while (l < r) {
    long long mid = l + r >> 1;
    z = q - mid;
    w = q + mid + 1;
    if (f(x, y - z, y, b) + f(x, y - w, y, a - 1) - f(x, y - z, y, a - 1) -
            f(x, y - w, y, b) >
        0)
      r = mid;
    else
      l = mid + 1;
  }
  k = exgcd(x, y, z, w);
  ans = 1000000000;
  x /= k;
  y /= k;
  if ((q - l) % k == 0) {
    c = (q - l) / k * z;
    c += (a - c) / y * y;
    while (c >= a) c -= y;
    while (c < a) c += y;
    ans = min(ans, c);
  }
  if ((q + l) % k == 0) {
    c = (q + l) / k * z;
    c += (a - c) / y * y;
    while (c >= a) c -= y;
    while (c < a) c += y;
    ans = min(ans, c);
  }
  printf("%lld\n", ans);
}
signed main() {
  long long qwq = read();
  while (qwq--) mian();
  return 0;
}

```