#include <bits/stdc++.h>
using namespace std;
inline bool EQ(double a, double b) { return fabs(a - b) < 1e-9; }
const long long int INF = 1 << 29;
inline long long int two(long long int n) { return 1 << n; }
inline long long int test(long long int n, long long int b) {
  return (n >> b) & 1;
}
inline void set_bit(long long int &n, long long int b) { n |= two(b); }
inline void unset_bit(long long int &n, long long int b) { n &= ~two(b); }
inline long long int last_bit(long long int n) { return n & (-n); }
inline long long int ones(long long int n) {
  long long int res = 0;
  while (n && ++res) n -= n & (-n);
  return res;
}
long long int gcd(long long int a, long long int b, long long int &x,
                  long long int &y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  long long int x1, y1;
  long long int d = gcd(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return d;
}
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);
}
bool find_any_solution(long long int a, long long int b, long long int c,
                       long long int &x0, long long int &y0, long long int &g) {
  g = gcd(abs(a), abs(b), x0, y0);
  if (c % g) {
    return false;
  }
  solve(abs(a), abs(b), x0, y0);
  x0 *= (c / g) * (abs(a) / a);
  y0 *= (c / g) * (abs(b) / b);
  long long int c1 = abs(a) / g;
  long long int c2 = abs(b) / g;
  long long int shift = min(x0 / c2, y0 / c1);
  x0 -= shift * c2;
  y0 -= shift * c1;
  while (x0 < 0 || y0 < 0) {
    x0 += c2;
    y0 += c1;
  }
  while (x0 >= c2 && y0 >= c1) {
    x0 -= c2;
    y0 -= c1;
  }
  return true;
}
long long int loot(long long int a, long long int b) {
  return a % b != 0 ? a / b : a / b - 1;
}
int main() {
  long long int a1, b1, a2, b2, l, r, x, y, g;
  cin >> a1 >> b1 >> a2 >> b2 >> l >> r;
  l = max(l, max(b1, b2));
  if (l > r) {
    cout << 0;
    return 0;
  }
  bool f = find_any_solution(a1, -a2, b2 - b1, x, y, g);
  if (!f) {
    cout << 0;
    return 0;
  }
  long long int num = a1 * x + b1;
  long long int ans = 0;
  g = ((a1 * a2) / g);
  if (num < l) {
    ans -= loot(l - num, g);
    ans += (r - num) / g;
  } else if (num > r) {
    ans -= loot(num - r, g);
    ans += (num - l) / g;
  } else {
    ans += (num - l) / g;
    ans += (r - num) / g;
    ans++;
  }
  cout << ans;
}

### 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;
inline bool EQ(double a, double b) { return fabs(a - b) < 1e-9; }
const long long int INF = 1 << 29;
inline long long int two(long long int n) { return 1 << n; }
inline long long int test(long long int n, long long int b) {
  return (n >> b) & 1;
}
inline void set_bit(long long int &n, long long int b) { n |= two(b); }
inline void unset_bit(long long int &n, long long int b) { n &= ~two(b); }
inline long long int last_bit(long long int n) { return n & (-n); }
inline long long int ones(long long int n) {
  long long int res = 0;
  while (n && ++res) n -= n & (-n);
  return res;
}
long long int gcd(long long int a, long long int b, long long int &x,
                  long long int &y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  long long int x1, y1;
  long long int d = gcd(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return d;
}
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);
}
bool find_any_solution(long long int a, long long int b, long long int c,
                       long long int &x0, long long int &y0, long long int &g) {
  g = gcd(abs(a), abs(b), x0, y0);
  if (c % g) {
    return false;
  }
  solve(abs(a), abs(b), x0, y0);
  x0 *= (c / g) * (abs(a) / a);
  y0 *= (c / g) * (abs(b) / b);
  long long int c1 = abs(a) / g;
  long long int c2 = abs(b) / g;
  long long int shift = min(x0 / c2, y0 / c1);
  x0 -= shift * c2;
  y0 -= shift * c1;
  while (x0 < 0 || y0 < 0) {
    x0 += c2;
    y0 += c1;
  }
  while (x0 >= c2 && y0 >= c1) {
    x0 -= c2;
    y0 -= c1;
  }
  return true;
}
long long int loot(long long int a, long long int b) {
  return a % b != 0 ? a / b : a / b - 1;
}
int main() {
  long long int a1, b1, a2, b2, l, r, x, y, g;
  cin >> a1 >> b1 >> a2 >> b2 >> l >> r;
  l = max(l, max(b1, b2));
  if (l > r) {
    cout << 0;
    return 0;
  }
  bool f = find_any_solution(a1, -a2, b2 - b1, x, y, g);
  if (!f) {
    cout << 0;
    return 0;
  }
  long long int num = a1 * x + b1;
  long long int ans = 0;
  g = ((a1 * a2) / g);
  if (num < l) {
    ans -= loot(l - num, g);
    ans += (r - num) / g;
  } else if (num > r) {
    ans -= loot(num - r, g);
    ans += (num - l) / g;
  } else {
    ans += (num - l) / g;
    ans += (r - num) / g;
    ans++;
  }
  cout << ans;
}

```