#include <bits/stdc++.h>
using namespace std;
long long a[2], b[2], L, R;
long long exgcd(long long a, long long b, long long &x, long long &y) {
  if (a == 0) {
    x = 0, y = 1;
    return b;
  }
  long long g = exgcd(b % a, a, x, y), p = y;
  y = x, x = p - b / a * x;
  return g;
}
long long QMulty(long long a, long long b, long long mod) {
  long long res = 0;
  a %= mod, b %= mod;
  while (a > 0) {
    if (a & 1) res = (res + b) % mod;
    b = (b + b) % mod, a >>= 1;
  }
  return res;
}
int main() {
  cin >> a[0] >> b[0] >> a[1] >> b[1] >> L >> R;
  long long x, y, g = exgcd(a[0], a[1], x, y), p, v;
  if ((-b[0] + b[1]) % g != 0)
    cout << 0 << endl;
  else {
    exgcd(a[0], a[1], x, y);
    p = a[0] * a[1] / g;
    x = x * (-b[0] + b[1]) / g, y = y * (-b[0] + b[1]) / g;
    L = max(L, b[0]), L = max(L, b[1]);
    x = QMulty(a[0], x, p) + b[0];
    x = x + (L - x) / p * p;
    while (x < L) x += p;
    while (x - p >= L) x -= p;
    y = x + (R - x) / p * p;
    while (y + p <= R) y += p;
    while (y > R) y -= p;
    if (x > y)
      cout << 0 << endl;
    else
      cout << (y - x) / p + 1 << endl;
  }
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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 a[2], b[2], L, R;
long long exgcd(long long a, long long b, long long &x, long long &y) {
  if (a == 0) {
    x = 0, y = 1;
    return b;
  }
  long long g = exgcd(b % a, a, x, y), p = y;
  y = x, x = p - b / a * x;
  return g;
}
long long QMulty(long long a, long long b, long long mod) {
  long long res = 0;
  a %= mod, b %= mod;
  while (a > 0) {
    if (a & 1) res = (res + b) % mod;
    b = (b + b) % mod, a >>= 1;
  }
  return res;
}
int main() {
  cin >> a[0] >> b[0] >> a[1] >> b[1] >> L >> R;
  long long x, y, g = exgcd(a[0], a[1], x, y), p, v;
  if ((-b[0] + b[1]) % g != 0)
    cout << 0 << endl;
  else {
    exgcd(a[0], a[1], x, y);
    p = a[0] * a[1] / g;
    x = x * (-b[0] + b[1]) / g, y = y * (-b[0] + b[1]) / g;
    L = max(L, b[0]), L = max(L, b[1]);
    x = QMulty(a[0], x, p) + b[0];
    x = x + (L - x) / p * p;
    while (x < L) x += p;
    while (x - p >= L) x -= p;
    y = x + (R - x) / p * p;
    while (y + p <= R) y += p;
    while (y > R) y -= p;
    if (x > y)
      cout << 0 << endl;
    else
      cout << (y - x) / p + 1 << endl;
  }
  return 0;
}

```