#include <bits/stdc++.h>
using namespace std;
long long exgcd(const long long &a, const long long &b, long long &x,
                long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  } else {
    long long r = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return r;
  }
}
inline long long mul(long long x, long long y, const long long &mod) {
  long long ret = 0;
  if (y < 0) {
    y = -y;
    x = -x;
  }
  while (y) {
    if (y & 1) ret = (ret + x) % mod;
    x = (x << 1) % mod;
    y >>= 1;
  }
  return ret;
}
int main() {
  long long a1, a2, b1, b2, l, r, x, y, g, lcm, f, ans = 0;
  scanf("%lld%lld%lld%lld%lld%lld", &a1, &b1, &a2, &b2, &l, &r);
  l = max(l, max(b1, b2));
  g = exgcd(a1, a2, x, y);
  if ((b2 - b1) % g == 0 && l <= r) {
    lcm = a1 / g * a2;
    x = mul(x, (b2 - b1) / g, lcm);
    f = (mul(x, a1, lcm) + b1) % lcm;
    if (f < l) {
      f += (l - f + lcm - 1) / lcm * lcm;
    }
    f -= (f - l) / lcm * lcm;
    ans = (r - f + lcm) / lcm;
    printf("%lld\n", ans);
  } else {
    puts("0");
  }
  return 0;
}

### Prompt

In Cpp, your task is to solve 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 exgcd(const long long &a, const long long &b, long long &x,
                long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  } else {
    long long r = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return r;
  }
}
inline long long mul(long long x, long long y, const long long &mod) {
  long long ret = 0;
  if (y < 0) {
    y = -y;
    x = -x;
  }
  while (y) {
    if (y & 1) ret = (ret + x) % mod;
    x = (x << 1) % mod;
    y >>= 1;
  }
  return ret;
}
int main() {
  long long a1, a2, b1, b2, l, r, x, y, g, lcm, f, ans = 0;
  scanf("%lld%lld%lld%lld%lld%lld", &a1, &b1, &a2, &b2, &l, &r);
  l = max(l, max(b1, b2));
  g = exgcd(a1, a2, x, y);
  if ((b2 - b1) % g == 0 && l <= r) {
    lcm = a1 / g * a2;
    x = mul(x, (b2 - b1) / g, lcm);
    f = (mul(x, a1, lcm) + b1) % lcm;
    if (f < l) {
      f += (l - f + lcm - 1) / lcm * lcm;
    }
    f -= (f - l) / lcm * lcm;
    ans = (r - f + lcm) / lcm;
    printf("%lld\n", ans);
  } else {
    puts("0");
  }
  return 0;
}

```