#include <bits/stdc++.h>
using namespace std;
long long a, b, p, q;
int gcd(int a, int b) {
  if (a < b) swap(a, b);
  while (b != 0) {
    int c = a % b;
    a = b;
    b = c;
  }
  return a;
}
pair<int, int> lc(int a, int b) {
  assert(a * b != 0);
  if (b == 1) return {0, 1};
  if (a == 1) return {1, 0};
  int x1, y1;
  tie(x1, y1) = lc(b, a % b);
  return {y1, x1 - (a / b) * y1};
}
int inv(int a, int m) {
  pair<int, int> p = lc(a, m);
  return ((p.first % m) + m) % m;
}
int brute() {
  double best = q;
  int bestx;
  for (int x = a; x <= min(b, a + q); x++) {
    unsigned long long ris = (p * x) % q;
    if (fabs(ris - q / 2.) < best) {
      best = fabs(ris - q / 2.);
      bestx = x;
    }
  }
  return bestx;
}
int solve() {
  int t = gcd(p, q);
  p /= t;
  q /= t;
  if (b - a < 1e5 || q < 1e5) return brute();
  long long rs = (q / 2 - a * p) % q;
  rs = (rs + q) % q;
  long long rs2 = rs;
  if (q % 2) rs2++;
  long long invp = inv(p, q) % q;
  while (1) {
    long long y1, y2;
    y1 = (invp * rs) % q;
    y2 = (invp * rs2) % q;
    long long d1 = 0, d2 = 0;
    long long v1 = abs(2 * (((y1 + a) * p) % q) - q);
    long long v2 = abs(2 * (((y2 + a) * p) % q) - q);
    long long y = LLONG_MAX;
    if (v1 <= v2) {
      y = min(y, y1);
      d1 = max(1LL, (y1 - b) / invp);
    }
    if (v2 <= v1) {
      y = min(y, y2);
      d2 = max(1LL, (q - y2) / invp);
    }
    if (y <= b - a) return a + y;
    rs = (rs + q - d1) % q;
    rs2 = (rs2 + d2) % q;
  }
}
int main() {
  int t;
  cin >> t;
  for (int i = 0; i < t; i++) {
    cin >> a >> b >> p >> q;
    cout << solve() << endl;
  }
}

### Prompt

Your challenge is to write 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 a, b, p, q;
int gcd(int a, int b) {
  if (a < b) swap(a, b);
  while (b != 0) {
    int c = a % b;
    a = b;
    b = c;
  }
  return a;
}
pair<int, int> lc(int a, int b) {
  assert(a * b != 0);
  if (b == 1) return {0, 1};
  if (a == 1) return {1, 0};
  int x1, y1;
  tie(x1, y1) = lc(b, a % b);
  return {y1, x1 - (a / b) * y1};
}
int inv(int a, int m) {
  pair<int, int> p = lc(a, m);
  return ((p.first % m) + m) % m;
}
int brute() {
  double best = q;
  int bestx;
  for (int x = a; x <= min(b, a + q); x++) {
    unsigned long long ris = (p * x) % q;
    if (fabs(ris - q / 2.) < best) {
      best = fabs(ris - q / 2.);
      bestx = x;
    }
  }
  return bestx;
}
int solve() {
  int t = gcd(p, q);
  p /= t;
  q /= t;
  if (b - a < 1e5 || q < 1e5) return brute();
  long long rs = (q / 2 - a * p) % q;
  rs = (rs + q) % q;
  long long rs2 = rs;
  if (q % 2) rs2++;
  long long invp = inv(p, q) % q;
  while (1) {
    long long y1, y2;
    y1 = (invp * rs) % q;
    y2 = (invp * rs2) % q;
    long long d1 = 0, d2 = 0;
    long long v1 = abs(2 * (((y1 + a) * p) % q) - q);
    long long v2 = abs(2 * (((y2 + a) * p) % q) - q);
    long long y = LLONG_MAX;
    if (v1 <= v2) {
      y = min(y, y1);
      d1 = max(1LL, (y1 - b) / invp);
    }
    if (v2 <= v1) {
      y = min(y, y2);
      d2 = max(1LL, (q - y2) / invp);
    }
    if (y <= b - a) return a + y;
    rs = (rs + q - d1) % q;
    rs2 = (rs2 + d2) % q;
  }
}
int main() {
  int t;
  cin >> t;
  for (int i = 0; i < t; i++) {
    cin >> a >> b >> p >> q;
    cout << solve() << endl;
  }
}

```