#include <bits/stdc++.h>
using namespace std;
int chh;
const int N = 1005;
long long a[N], m[N];
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
void extend_Euclid(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return;
  }
  extend_Euclid(b, a % b, x, y);
  long long tmp = x;
  x = y;
  y = tmp - (a / b) * y;
}
long long Inv(long long a, long long b) {
  long long d = gcd(a, b);
  if (d != 1) return -1;
  long long x, y;
  extend_Euclid(a, b, x, y);
  return (x % b + b) % b;
}
bool merge(long long a1, long long m1, long long a2, long long m2,
           long long &a3, long long &m3) {
  long long d = gcd(m1, m2);
  long long c = a2 - a1;
  if (c % d) return false;
  c = (c % m2 + m2) % m2;
  m1 /= d;
  m2 /= d;
  c /= d;
  c *= Inv(m1, m2);
  c %= m2;
  c *= m1 * d;
  c += a1;
  m3 = m1 * m2 * d;
  a3 = (c % m3 + m3) % m3;
  return true;
}
long long CRT(long long a[], long long m[], int n) {
  long long a1 = a[1];
  long long m1 = m[1];
  for (int i = 2; i <= n; i++) {
    long long a2 = a[i];
    long long m2 = m[i];
    long long m3, a3;
    if (!merge(a1, m1, a2, m2, a3, m3)) return -1;
    a1 = a3;
    m1 = m3;
  }
  return (a1 % m1 + m1) % m1;
}
int a1, b1, a2, b2, L, R;
int main() {
  long long ans, res, l, r, d, n;
  while (~scanf("%d %d %d %d %d %d", &a1, &b1, &a2, &b2, &L, &R)) {
    L = max(L, b1);
    L = max(L, b2);
    n = 2;
    a[1] = b1, a[2] = b2;
    m[1] = a1, m[2] = a2;
    ans = CRT(a, m, n);
    if (ans == -1) {
      puts("0");
      continue;
    }
    d = m[1] * m[2] / gcd(m[1], m[2]);
    l = (L - ans) / d * d + ans;
    while (l < L) l += d;
    r = (R - ans) / d * d + ans;
    while (r <= R) r += d;
    r -= d;
    if (l > r)
      res = 0;
    else
      res = (r - l) / d + 1;
    cout << res << '\n';
  }
  return 0;
}

### Prompt

Generate 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;
int chh;
const int N = 1005;
long long a[N], m[N];
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
void extend_Euclid(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return;
  }
  extend_Euclid(b, a % b, x, y);
  long long tmp = x;
  x = y;
  y = tmp - (a / b) * y;
}
long long Inv(long long a, long long b) {
  long long d = gcd(a, b);
  if (d != 1) return -1;
  long long x, y;
  extend_Euclid(a, b, x, y);
  return (x % b + b) % b;
}
bool merge(long long a1, long long m1, long long a2, long long m2,
           long long &a3, long long &m3) {
  long long d = gcd(m1, m2);
  long long c = a2 - a1;
  if (c % d) return false;
  c = (c % m2 + m2) % m2;
  m1 /= d;
  m2 /= d;
  c /= d;
  c *= Inv(m1, m2);
  c %= m2;
  c *= m1 * d;
  c += a1;
  m3 = m1 * m2 * d;
  a3 = (c % m3 + m3) % m3;
  return true;
}
long long CRT(long long a[], long long m[], int n) {
  long long a1 = a[1];
  long long m1 = m[1];
  for (int i = 2; i <= n; i++) {
    long long a2 = a[i];
    long long m2 = m[i];
    long long m3, a3;
    if (!merge(a1, m1, a2, m2, a3, m3)) return -1;
    a1 = a3;
    m1 = m3;
  }
  return (a1 % m1 + m1) % m1;
}
int a1, b1, a2, b2, L, R;
int main() {
  long long ans, res, l, r, d, n;
  while (~scanf("%d %d %d %d %d %d", &a1, &b1, &a2, &b2, &L, &R)) {
    L = max(L, b1);
    L = max(L, b2);
    n = 2;
    a[1] = b1, a[2] = b2;
    m[1] = a1, m[2] = a2;
    ans = CRT(a, m, n);
    if (ans == -1) {
      puts("0");
      continue;
    }
    d = m[1] * m[2] / gcd(m[1], m[2]);
    l = (L - ans) / d * d + ans;
    while (l < L) l += d;
    r = (R - ans) / d * d + ans;
    while (r <= R) r += d;
    r -= d;
    if (l > r)
      res = 0;
    else
      res = (r - l) / d + 1;
    cout << res << '\n';
  }
  return 0;
}

```