#include <bits/stdc++.h>
using namespace std;
long long a1, b1, a2, b2, x1, x2, t, l, r;
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 g = exgcd(b, a % b, y, x);
  y = y - a / b * x;
  return g;
}
int main() {
  scanf("%lld%lld%lld%lld%lld%lld", &a1, &b1, &a2, &b2, &l, &r);
  long long g = exgcd(a1, a2, x1, x2), m = a1 * a2 / g;
  if ((b2 - b1) % g) {
    puts("0");
    return 0;
  }
  x1 *= (b2 - b1) / g;
  long long xx = m / a1;
  x2 *= (b1 - b2) / g;
  long long yy = m / a2;
  long long l1 = max(0ll, (l - b1) / a1 + (l > b1 && (l - b1) % a1 != 0));
  long long l2 = max(0ll, (l - b2) / a2 + (l > b2 && (l - b2) % a2 != 0));
  long long r1 = (r - b1) / a1 - (r < b1 && (r - b1) % a1 != 0);
  long long r2 = (r - b2) / a2 - (r < b2 && (r - b2) % a2 != 0);
  t = max((l1 - x1) / xx, (l2 - x2) / yy);
  x1 += t * xx, x2 += t * yy;
  if (x1 < l1 || x2 < l2) x1 += xx, x2 += yy;
  printf("%lld",
         r1 < x1 || r2 < x2 ? 0 : min((r1 - x1) / xx, (r2 - x2) / yy) + 1);
  return 0;
}

### Prompt

Your task is to create a cpp solution to the following problem:

You are given two arithmetic progressions: a1k + b1 and a2l + b2. Find the number of integers x such that L ≤ x ≤ R and x = a1k' + b1 = a2l' + b2, for some integers k', l' ≥ 0.

Input

The only line contains six integers a1, b1, a2, b2, L, R (0 < a1, a2 ≤ 2·109, - 2·109 ≤ b1, b2, L, R ≤ 2·109, L ≤ R).

Output

Print the desired number of integers x.

Examples

Input

2 0 3 3 5 21


Output

3


Input

2 4 3 0 6 17


Output

2

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long a1, b1, a2, b2, x1, x2, t, l, r;
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 g = exgcd(b, a % b, y, x);
  y = y - a / b * x;
  return g;
}
int main() {
  scanf("%lld%lld%lld%lld%lld%lld", &a1, &b1, &a2, &b2, &l, &r);
  long long g = exgcd(a1, a2, x1, x2), m = a1 * a2 / g;
  if ((b2 - b1) % g) {
    puts("0");
    return 0;
  }
  x1 *= (b2 - b1) / g;
  long long xx = m / a1;
  x2 *= (b1 - b2) / g;
  long long yy = m / a2;
  long long l1 = max(0ll, (l - b1) / a1 + (l > b1 && (l - b1) % a1 != 0));
  long long l2 = max(0ll, (l - b2) / a2 + (l > b2 && (l - b2) % a2 != 0));
  long long r1 = (r - b1) / a1 - (r < b1 && (r - b1) % a1 != 0);
  long long r2 = (r - b2) / a2 - (r < b2 && (r - b2) % a2 != 0);
  t = max((l1 - x1) / xx, (l2 - x2) / yy);
  x1 += t * xx, x2 += t * yy;
  if (x1 < l1 || x2 < l2) x1 += xx, x2 += yy;
  printf("%lld",
         r1 < x1 || r2 < x2 ? 0 : min((r1 - x1) / xx, (r2 - x2) / yy) + 1);
  return 0;
}

```