#include <bits/stdc++.h>
using namespace std;
void gcd(long long a, long long b, long long &d, long long &x, long long &y) {
  if (!b) {
    d = a;
    x = 1;
    y = 0;
  } else {
    gcd(b, a % b, d, y, x);
    y -= (a / b) * x;
  }
}
long long lbquotient(long long a, long long b) {
  if (a >= 0)
    return a / b;
  else {
    if (a % b == 0)
      return a / b;
    else
      return a / b - 1;
  }
}
long long lbmodulo(long long a, long long b) {
  if (a >= 0)
    return a % b;
  else {
    if (a % b == 0)
      return a % b;
    else
      return b - (-a) % b;
  }
}
long long a1, b1, a2, b2, L, R, ans, ff;
int main() {
  cin >> a1 >> b1 >> a2 >> b2 >> L >> R;
  long long kp, lp, GCD, LCM, MOD, l, r, la, ra;
  gcd(a1, a2, GCD, kp, lp);
  LCM = a1 / GCD * a2;
  if ((b2 - b1) % GCD) {
    cout << 0 << endl;
    return 0;
  }
  kp = (b2 - b1) / GCD * kp;
  lp = (b2 - b1) / GCD * lp;
  lp = -lp;
  ans = a1 * lbmodulo(kp, a2 / GCD) + b1;
  if (ans < 0) ans += (-ans / LCM + 1) * LCM;
  ans %= LCM;
  L = max(L, max(b1, b2));
  if (L > R)
    cout << 0 << endl;
  else {
    l = lbquotient(L, LCM);
    r = lbquotient(R, LCM);
    ff = r - l;
    if (l * LCM + ans < L) --ff;
    if (r * LCM + ans <= R) ++ff;
    cout << ff << endl;
  }
  return 0;
}

### 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;
void gcd(long long a, long long b, long long &d, long long &x, long long &y) {
  if (!b) {
    d = a;
    x = 1;
    y = 0;
  } else {
    gcd(b, a % b, d, y, x);
    y -= (a / b) * x;
  }
}
long long lbquotient(long long a, long long b) {
  if (a >= 0)
    return a / b;
  else {
    if (a % b == 0)
      return a / b;
    else
      return a / b - 1;
  }
}
long long lbmodulo(long long a, long long b) {
  if (a >= 0)
    return a % b;
  else {
    if (a % b == 0)
      return a % b;
    else
      return b - (-a) % b;
  }
}
long long a1, b1, a2, b2, L, R, ans, ff;
int main() {
  cin >> a1 >> b1 >> a2 >> b2 >> L >> R;
  long long kp, lp, GCD, LCM, MOD, l, r, la, ra;
  gcd(a1, a2, GCD, kp, lp);
  LCM = a1 / GCD * a2;
  if ((b2 - b1) % GCD) {
    cout << 0 << endl;
    return 0;
  }
  kp = (b2 - b1) / GCD * kp;
  lp = (b2 - b1) / GCD * lp;
  lp = -lp;
  ans = a1 * lbmodulo(kp, a2 / GCD) + b1;
  if (ans < 0) ans += (-ans / LCM + 1) * LCM;
  ans %= LCM;
  L = max(L, max(b1, b2));
  if (L > R)
    cout << 0 << endl;
  else {
    l = lbquotient(L, LCM);
    r = lbquotient(R, LCM);
    ff = r - l;
    if (l * LCM + ans < L) --ff;
    if (r * LCM + ans <= R) ++ff;
    cout << ff << endl;
  }
  return 0;
}

```