#include <bits/stdc++.h>
using namespace std;
long long a1, a2, b1, b2, L, R, g, x, y, xx, ans, ansl, ansr, d, A, B;
long long exgcd(long long a, long long b, long long &x, long long &y) {
  if (a == 0 && b == 0) return -1;
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = exgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
long long ceil1(long long n, long long k) {
  if (n > 0)
    return (n + k - 1) / k;
  else
    return n / k;
}
long long floor1(long long n, long long k) {
  if (n > 0)
    return n / k;
  else
    return (n - k + 1) / k;
}
int main() {
  cin >> a1 >> b1 >> a2 >> b2 >> L >> R;
  L = max(L, b1);
  L = max(L, b2);
  if (L > R) {
    printf("0\n");
    return 0;
  }
  A = a1;
  B = -a2;
  g = exgcd(A, B, x, y);
  if ((b2 - b1) % g != 0) {
    printf("0\n");
    return 0;
  }
  x = x * (b2 - b1) / g % (a2 / g);
  xx = a1 * x + b1;
  d = a1 * a2 / g;
  if (d < 0) d = -d;
  ans = ceil1(L - xx, d);
  ansl = xx + d * ans;
  ans = floor1(R - xx, d);
  ansr = xx + d * ans;
  printf("%I64d\n", (ansr - ansl) / d + 1);
  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;
long long a1, a2, b1, b2, L, R, g, x, y, xx, ans, ansl, ansr, d, A, B;
long long exgcd(long long a, long long b, long long &x, long long &y) {
  if (a == 0 && b == 0) return -1;
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = exgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
long long ceil1(long long n, long long k) {
  if (n > 0)
    return (n + k - 1) / k;
  else
    return n / k;
}
long long floor1(long long n, long long k) {
  if (n > 0)
    return n / k;
  else
    return (n - k + 1) / k;
}
int main() {
  cin >> a1 >> b1 >> a2 >> b2 >> L >> R;
  L = max(L, b1);
  L = max(L, b2);
  if (L > R) {
    printf("0\n");
    return 0;
  }
  A = a1;
  B = -a2;
  g = exgcd(A, B, x, y);
  if ((b2 - b1) % g != 0) {
    printf("0\n");
    return 0;
  }
  x = x * (b2 - b1) / g % (a2 / g);
  xx = a1 * x + b1;
  d = a1 * a2 / g;
  if (d < 0) d = -d;
  ans = ceil1(L - xx, d);
  ansl = xx + d * ans;
  ans = floor1(R - xx, d);
  ansr = xx + d * ans;
  printf("%I64d\n", (ansr - ansl) / d + 1);
  return 0;
}

```