#include <bits/stdc++.h>
using namespace std;
void solve(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return;
  }
  long long xx, yy;
  solve(b, a % b, xx, yy);
  x = yy;
  y = xx - yy * (a / b);
}
long long gcd(long long a, long long b) {
  while (a > 0 && b > 0) {
    if (a > b) {
      a %= b;
    } else {
      b %= a;
    }
  }
  return a + b;
}
int main() {
  long long a1, b1, a2, b2, L, R;
  cin >> a1 >> b1 >> a2 >> b2 >> L >> R;
  long long g = gcd(a1, a2);
  if ((b2 - b1) % g != 0) {
    cout << 0 << endl;
    return 0;
  }
  long long k, l;
  solve(a1, a2, k, l);
  k *= (b2 - b1) / g;
  l *= (b1 - b2) / g;
  long long c1 = a1 / g;
  long long c2 = a2 / g;
  long long shift = min(k / c2, l / c1);
  k -= shift * c2;
  l -= shift * c1;
  while (k < 0 || l < 0) {
    k += c2;
    l += c1;
  }
  while (k >= c2 && l >= c1) {
    k -= c2;
    l -= c1;
  }
  long long start = a1 * k + b1;
  assert(start == a2 * l + b2);
  long long step = a1 / g * a2;
  if (start < L) {
    start += (L - start) / step * step;
  }
  while (start < L) {
    start += step;
  }
  long long ans = 0;
  if (start <= R) {
    ans = (R - start) / step + 1;
  }
  cout << ans << endl;
  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;
void solve(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return;
  }
  long long xx, yy;
  solve(b, a % b, xx, yy);
  x = yy;
  y = xx - yy * (a / b);
}
long long gcd(long long a, long long b) {
  while (a > 0 && b > 0) {
    if (a > b) {
      a %= b;
    } else {
      b %= a;
    }
  }
  return a + b;
}
int main() {
  long long a1, b1, a2, b2, L, R;
  cin >> a1 >> b1 >> a2 >> b2 >> L >> R;
  long long g = gcd(a1, a2);
  if ((b2 - b1) % g != 0) {
    cout << 0 << endl;
    return 0;
  }
  long long k, l;
  solve(a1, a2, k, l);
  k *= (b2 - b1) / g;
  l *= (b1 - b2) / g;
  long long c1 = a1 / g;
  long long c2 = a2 / g;
  long long shift = min(k / c2, l / c1);
  k -= shift * c2;
  l -= shift * c1;
  while (k < 0 || l < 0) {
    k += c2;
    l += c1;
  }
  while (k >= c2 && l >= c1) {
    k -= c2;
    l -= c1;
  }
  long long start = a1 * k + b1;
  assert(start == a2 * l + b2);
  long long step = a1 / g * a2;
  if (start < L) {
    start += (L - start) / step * step;
  }
  while (start < L) {
    start += step;
  }
  long long ans = 0;
  if (start <= R) {
    ans = (R - start) / step + 1;
  }
  cout << ans << endl;
  return 0;
}

```