#include <bits/stdc++.h>
using namespace std;
template <typename T>
void chkmin(T &x, T y) {
  if (x > y) x = y;
}
int T, A, B, P, Q;
map<int, int> mp;
int f(int x) { return 2ll * P * x % (2 * Q); }
int add(int x) {
  if (x < 0) x += 2 * Q;
  return x;
}
pair<int, int> calc(int x) { return make_pair(abs(f(x) - Q), x); }
pair<int, int> sol() {
  int nq = add(Q - f(A));
  pair<int, int> res = make_pair(2 * Q, 2 * Q);
  auto it = mp.lower_bound(nq);
  if (it == mp.end()) it = mp.begin();
  if (it != mp.end()) chkmin(res, make_pair(add(it->first - nq), it->second));
  if (it == mp.begin()) it = mp.end();
  it = prev(it);
  chkmin(res, make_pair(add(nq - it->first), it->second));
  return make_pair(res.first, res.second + A);
}
void solve() {
  int len = sqrt(B - A + 1);
  mp.clear();
  for (int i = len - 1; ~i; i--) mp[f(i)] = i;
  pair<int, int> ans = make_pair(2 * Q, 2 * Q);
  for (; A + len - 1 <= B; A += len) chkmin(ans, sol());
  for (; A <= B; A++) chkmin(ans, calc(A));
  printf("%d\n", ans.second);
}
int main() {
  cin >> T;
  while (T--) {
    cin >> A >> B >> P >> Q;
    solve();
  }
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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;
template <typename T>
void chkmin(T &x, T y) {
  if (x > y) x = y;
}
int T, A, B, P, Q;
map<int, int> mp;
int f(int x) { return 2ll * P * x % (2 * Q); }
int add(int x) {
  if (x < 0) x += 2 * Q;
  return x;
}
pair<int, int> calc(int x) { return make_pair(abs(f(x) - Q), x); }
pair<int, int> sol() {
  int nq = add(Q - f(A));
  pair<int, int> res = make_pair(2 * Q, 2 * Q);
  auto it = mp.lower_bound(nq);
  if (it == mp.end()) it = mp.begin();
  if (it != mp.end()) chkmin(res, make_pair(add(it->first - nq), it->second));
  if (it == mp.begin()) it = mp.end();
  it = prev(it);
  chkmin(res, make_pair(add(nq - it->first), it->second));
  return make_pair(res.first, res.second + A);
}
void solve() {
  int len = sqrt(B - A + 1);
  mp.clear();
  for (int i = len - 1; ~i; i--) mp[f(i)] = i;
  pair<int, int> ans = make_pair(2 * Q, 2 * Q);
  for (; A + len - 1 <= B; A += len) chkmin(ans, sol());
  for (; A <= B; A++) chkmin(ans, calc(A));
  printf("%d\n", ans.second);
}
int main() {
  cin >> T;
  while (T--) {
    cin >> A >> B >> P >> Q;
    solve();
  }
  return 0;
}

```