#include <bits/stdc++.h>
using namespace std;
long long m1, m2, r1, r2, l, r;
long long ans1, ans2;
long long exgcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long ret = exgcd(b, a % b, x, y), tmp = y;
  y = x - a / b * y;
  x = tmp;
  return ret;
}
void Ex_crt() {
  ans1 = m1;
  ans2 = r1;
  long long x, y, gcd;
  gcd = exgcd(ans1, m2, x, y);
  if ((r2 - ans2) % gcd) {
    ans1 = -1;
    return;
  }
  long long lcm = ans1 / gcd * m2;
  x = x * (r2 - ans2) / gcd;
  y = y * (r2 - ans2) / gcd;
  long long add = m2 / gcd;
  x = (x % add + add) % add;
  ans2 = lcm;
  ans1 = r1 + x * m1;
  ans1 = (ans1 % ans2 + ans2) % ans2;
}
int main() {
  cin >> m1 >> r1 >> m2 >> r2 >> l >> r;
  Ex_crt();
  l = max(l, max(r1, r2));
  if (ans1 == -1 || l > r) {
    puts("0");
    return 0;
  }
  long long ans;
  ans = floor((double)(r - ans1) / ans2) - floor((double)(l - ans1) / ans2);
  if ((l - ans1) % ans2 == 0) ans++;
  printf("%I64d", ans);
  return 0;
}

### Prompt

Your task is to create 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 m1, m2, r1, r2, l, r;
long long ans1, ans2;
long long exgcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long ret = exgcd(b, a % b, x, y), tmp = y;
  y = x - a / b * y;
  x = tmp;
  return ret;
}
void Ex_crt() {
  ans1 = m1;
  ans2 = r1;
  long long x, y, gcd;
  gcd = exgcd(ans1, m2, x, y);
  if ((r2 - ans2) % gcd) {
    ans1 = -1;
    return;
  }
  long long lcm = ans1 / gcd * m2;
  x = x * (r2 - ans2) / gcd;
  y = y * (r2 - ans2) / gcd;
  long long add = m2 / gcd;
  x = (x % add + add) % add;
  ans2 = lcm;
  ans1 = r1 + x * m1;
  ans1 = (ans1 % ans2 + ans2) % ans2;
}
int main() {
  cin >> m1 >> r1 >> m2 >> r2 >> l >> r;
  Ex_crt();
  l = max(l, max(r1, r2));
  if (ans1 == -1 || l > r) {
    puts("0");
    return 0;
  }
  long long ans;
  ans = floor((double)(r - ans1) / ans2) - floor((double)(l - ans1) / ans2);
  if ((l - ans1) % ans2 == 0) ans++;
  printf("%I64d", ans);
  return 0;
}

```