#include <bits/stdc++.h>
using namespace std;
struct Item {
  long long m, r;
};
long long extgcd(long long a, long long b, long long& x, long long& y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  } else {
    long long d = extgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
  }
}
Item extcrt(const vector<Item>& v) {
  long long m1 = v[0].m, r1 = v[0].r, x, y;
  for (int i = 1; i < int(v.size()); i++) {
    long long m2 = v[i].m, r2 = v[i].r;
    long long g = extgcd(m1, m2, x, y);
    if ((r2 - r1) % g != 0) return {-1, -1};
    long long k = (r2 - r1) / g * x % (m2 / g);
    k = (k + m2 / g) % (m2 / g);
    long long m = m1 * m2 / g;
    long long r = (m1 * k + r1) % m;
    m1 = m;
    r1 = (r + m) % m;
  }
  return (Item){m1, r1};
}
int main() {
  long long a1, b1, a2, b2, L, R;
  scanf("%lld %lld %lld %lld %lld %lld", &a1, &b1, &a2, &b2, &L, &R);
  vector<Item> item;
  item.push_back((Item){a1, (b1 % a1 + a1) % a1});
  item.push_back((Item){a2, (b2 % a2 + a2) % a2});
  Item res = extcrt(item);
  if (res.m == -1) {
    puts("0");
    return 0;
  }
  L = max(L, max(b1, b2));
  long long s = (L - res.r) / res.m * res.m + res.r;
  long long t = (R - res.r) / res.m * res.m + res.r;
  if (s < L) s += res.m;
  if (t > R) t -= res.m;
  if (s > R || t < L) {
    puts("0");
    return 0;
  }
  long long ans = (t - s) / res.m + 1;
  printf("%lld\n", ans);
  return 0;
}

### Prompt

Create a solution in cpp for 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;
struct Item {
  long long m, r;
};
long long extgcd(long long a, long long b, long long& x, long long& y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  } else {
    long long d = extgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
  }
}
Item extcrt(const vector<Item>& v) {
  long long m1 = v[0].m, r1 = v[0].r, x, y;
  for (int i = 1; i < int(v.size()); i++) {
    long long m2 = v[i].m, r2 = v[i].r;
    long long g = extgcd(m1, m2, x, y);
    if ((r2 - r1) % g != 0) return {-1, -1};
    long long k = (r2 - r1) / g * x % (m2 / g);
    k = (k + m2 / g) % (m2 / g);
    long long m = m1 * m2 / g;
    long long r = (m1 * k + r1) % m;
    m1 = m;
    r1 = (r + m) % m;
  }
  return (Item){m1, r1};
}
int main() {
  long long a1, b1, a2, b2, L, R;
  scanf("%lld %lld %lld %lld %lld %lld", &a1, &b1, &a2, &b2, &L, &R);
  vector<Item> item;
  item.push_back((Item){a1, (b1 % a1 + a1) % a1});
  item.push_back((Item){a2, (b2 % a2 + a2) % a2});
  Item res = extcrt(item);
  if (res.m == -1) {
    puts("0");
    return 0;
  }
  L = max(L, max(b1, b2));
  long long s = (L - res.r) / res.m * res.m + res.r;
  long long t = (R - res.r) / res.m * res.m + res.r;
  if (s < L) s += res.m;
  if (t > R) t -= res.m;
  if (s > R || t < L) {
    puts("0");
    return 0;
  }
  long long ans = (t - s) / res.m + 1;
  printf("%lld\n", ans);
  return 0;
}

```