#include <bits/stdc++.h>
using namespace std;
long long int gcd(long long int a, long long int b) {
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}
int main() {
  long long int i, a[70][2] = {0}, a1, b1, a2, b2, l, r, x, y, g, ans, c, temp,
                   g1, g2;
  scanf("%lld%lld%lld%lld%lld%lld", &a1, &b1, &a2, &b2, &l, &r);
  if (a1 < a2) {
    temp = a1;
    a1 = a2;
    a2 = temp;
    temp = b1;
    b1 = b2;
    b2 = temp;
  }
  g = gcd(a1, a2);
  if ((abs(b2 - b1) % g) == 0) {
    x = a1 / g;
    y = a2 / g;
    i = 0;
    c = (b2 - b1) / g;
    if (y != 1) {
      while (y != 1) {
        a[i][0] = 1;
        a[i++][1] = -1 * (x / y);
        temp = y;
        y = x % y;
        x = temp;
      }
      i--;
      while (i >= 1) {
        temp = a[i][1] * a[i - 1][0];
        a[i - 1][1] = a[i][0] + a[i][1] * a[i - 1][1];
        a[i - 1][0] = temp;
        i--;
      }
    } else {
      a[0][0] = 1;
      a[0][1] = 1 - 1 * (x / y);
    }
    x = c * a[0][0];
    y = (-1) * c * a[0][1];
    g1 = a1 / g;
    g2 = a2 / g;
    if (x < 0) {
      temp = ceil((-1.0 * x) / g2);
    } else
      temp = (-1) * (x / g2);
    if (y < 0) {
      g = ceil((-1.0 * y) / g1);
    } else
      g = (-1) * (y / g1);
    temp = max(temp, g);
    x = x + g2 * temp;
    y = y + g1 * temp;
    g = gcd(a1, a2);
    temp = (a1 * a2) / g;
    y = b1 + a1 * x;
    if (y > r)
      ans = 0;
    else if (y >= l)
      ans = (r - y) / temp + 1;
    else {
      ans = (r - y) / temp - (l - y - 1) / temp;
    }
  } else
    ans = 0;
  printf("%lld\n", ans);
  return 0;
}

### Prompt

Develop a solution in CPP to the problem described below:

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 int gcd(long long int a, long long int b) {
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}
int main() {
  long long int i, a[70][2] = {0}, a1, b1, a2, b2, l, r, x, y, g, ans, c, temp,
                   g1, g2;
  scanf("%lld%lld%lld%lld%lld%lld", &a1, &b1, &a2, &b2, &l, &r);
  if (a1 < a2) {
    temp = a1;
    a1 = a2;
    a2 = temp;
    temp = b1;
    b1 = b2;
    b2 = temp;
  }
  g = gcd(a1, a2);
  if ((abs(b2 - b1) % g) == 0) {
    x = a1 / g;
    y = a2 / g;
    i = 0;
    c = (b2 - b1) / g;
    if (y != 1) {
      while (y != 1) {
        a[i][0] = 1;
        a[i++][1] = -1 * (x / y);
        temp = y;
        y = x % y;
        x = temp;
      }
      i--;
      while (i >= 1) {
        temp = a[i][1] * a[i - 1][0];
        a[i - 1][1] = a[i][0] + a[i][1] * a[i - 1][1];
        a[i - 1][0] = temp;
        i--;
      }
    } else {
      a[0][0] = 1;
      a[0][1] = 1 - 1 * (x / y);
    }
    x = c * a[0][0];
    y = (-1) * c * a[0][1];
    g1 = a1 / g;
    g2 = a2 / g;
    if (x < 0) {
      temp = ceil((-1.0 * x) / g2);
    } else
      temp = (-1) * (x / g2);
    if (y < 0) {
      g = ceil((-1.0 * y) / g1);
    } else
      g = (-1) * (y / g1);
    temp = max(temp, g);
    x = x + g2 * temp;
    y = y + g1 * temp;
    g = gcd(a1, a2);
    temp = (a1 * a2) / g;
    y = b1 + a1 * x;
    if (y > r)
      ans = 0;
    else if (y >= l)
      ans = (r - y) / temp + 1;
    else {
      ans = (r - y) / temp - (l - y - 1) / temp;
    }
  } else
    ans = 0;
  printf("%lld\n", ans);
  return 0;
}

```