#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
long long n, m, t;
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 g = exgcd(b, a % b, y, x);
  y -= a / b * x;
  return g;
}
int main(void) {
  long long a1, a2, b1, b2, l, r, x, y;
  cin >> a1 >> b1 >> a2 >> b2 >> l >> r;
  long long g = exgcd(a1, a2, x, y);
  long long c = b2 - b1;
  if (c % g != 0) {
    cout << 0;
    return 0;
  }
  m = a1 * a2 / g;
  x = x * c / g % (a2 / g);
  x = ((a1 * x) % m + b1 + m) % m;
  x += (max(b1, b2) - 1) / m * m;
  while (x > max(b1, b2)) x -= m;
  while (x < max(b1, b2)) x += m;
  long long cntl = x <= l ? (l - x) / m + 1 : 0;
  long long ans = x <= r ? (r - x) / m + 1 : 0;
  if (x <= l && (l - x) % m == 0) ans++;
  cout << ans - cntl;
  return 0;
}

### Prompt

Your challenge is to write 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;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
long long n, m, t;
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 g = exgcd(b, a % b, y, x);
  y -= a / b * x;
  return g;
}
int main(void) {
  long long a1, a2, b1, b2, l, r, x, y;
  cin >> a1 >> b1 >> a2 >> b2 >> l >> r;
  long long g = exgcd(a1, a2, x, y);
  long long c = b2 - b1;
  if (c % g != 0) {
    cout << 0;
    return 0;
  }
  m = a1 * a2 / g;
  x = x * c / g % (a2 / g);
  x = ((a1 * x) % m + b1 + m) % m;
  x += (max(b1, b2) - 1) / m * m;
  while (x > max(b1, b2)) x -= m;
  while (x < max(b1, b2)) x += m;
  long long cntl = x <= l ? (l - x) / m + 1 : 0;
  long long ans = x <= r ? (r - x) / m + 1 : 0;
  if (x <= l && (l - x) % m == 0) ans++;
  cout << ans - cntl;
  return 0;
}

```