#include <bits/stdc++.h>
using namespace std;
template <class T>
T abs(T x) {
  return x > 0 ? x : -x;
}
template <class T>
T gcd(T a, T b) {
  return a ? gcd(b % a, a) : b;
}
template <class T>
T sqr(T a) {
  return a * a;
}
template <class T>
T sgn(T a) {
  return a > 0 ? 1 : (a < 0 ? -1 : 0);
}
int n;
int m;
long long a1, b1, a2, b2, l, r;
long long power(long long a, long long b, long long mod) {
  long long c = 1;
  while (b) {
    if (b & 1) c = (c * a) % mod;
    a = (a * a) % mod;
    b /= 2;
  }
  return c;
}
long long phi(long long x) {
  long long cur = 1;
  for (long long i = 2; i * i <= x; i++)
    if (x % i == 0) {
      long long tmp = 1;
      while (x % i == 0) {
        x /= i;
        tmp *= i;
      }
      cur *= tmp - tmp / i;
    }
  if (x > 1) cur *= x - 1;
  return cur;
}
long long up(long long p, long long q) {
  if (p % q == 0) return p / q;
  return p / q + int(p > 0);
}
long long mul(long long a, long long b, long long mod) {
  long long c = 0;
  while (b) {
    if (b & 1) c = (c + a) % mod;
    a = (a + a) % mod;
    b /= 2;
  }
  return c;
}
int main() {
  cin >> a1 >> b1 >> a2 >> b2 >> l >> r;
  long long d = gcd(a1, a2);
  long long a = a1 * a2 / d;
  if ((b2 - b1) % d != 0)
    printf("0\n");
  else {
    long long p = (b2 - b1) / d;
    long long q = a1 / d;
    long long z = a2 / d;
    long long b = (mul(p * a1, power(q, phi(z) - 1, z), a) + b1) % a;
    long long t = max(up(b1 - b, a), up(b2 - b, a));
    l = max(l, a * t + b);
    if (l > r)
      cout << 0 << endl;
    else
      cout << (r - b) / a - (l > a * t + b ? (l - b - 1) / a : t - 1) << endl;
  }
  return 0;
}

### Prompt

Your challenge is to write 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;
template <class T>
T abs(T x) {
  return x > 0 ? x : -x;
}
template <class T>
T gcd(T a, T b) {
  return a ? gcd(b % a, a) : b;
}
template <class T>
T sqr(T a) {
  return a * a;
}
template <class T>
T sgn(T a) {
  return a > 0 ? 1 : (a < 0 ? -1 : 0);
}
int n;
int m;
long long a1, b1, a2, b2, l, r;
long long power(long long a, long long b, long long mod) {
  long long c = 1;
  while (b) {
    if (b & 1) c = (c * a) % mod;
    a = (a * a) % mod;
    b /= 2;
  }
  return c;
}
long long phi(long long x) {
  long long cur = 1;
  for (long long i = 2; i * i <= x; i++)
    if (x % i == 0) {
      long long tmp = 1;
      while (x % i == 0) {
        x /= i;
        tmp *= i;
      }
      cur *= tmp - tmp / i;
    }
  if (x > 1) cur *= x - 1;
  return cur;
}
long long up(long long p, long long q) {
  if (p % q == 0) return p / q;
  return p / q + int(p > 0);
}
long long mul(long long a, long long b, long long mod) {
  long long c = 0;
  while (b) {
    if (b & 1) c = (c + a) % mod;
    a = (a + a) % mod;
    b /= 2;
  }
  return c;
}
int main() {
  cin >> a1 >> b1 >> a2 >> b2 >> l >> r;
  long long d = gcd(a1, a2);
  long long a = a1 * a2 / d;
  if ((b2 - b1) % d != 0)
    printf("0\n");
  else {
    long long p = (b2 - b1) / d;
    long long q = a1 / d;
    long long z = a2 / d;
    long long b = (mul(p * a1, power(q, phi(z) - 1, z), a) + b1) % a;
    long long t = max(up(b1 - b, a), up(b2 - b, a));
    l = max(l, a * t + b);
    if (l > r)
      cout << 0 << endl;
    else
      cout << (r - b) / a - (l > a * t + b ? (l - b - 1) / a : t - 1) << endl;
  }
  return 0;
}

```