#include <bits/stdc++.h>
using namespace std;
long long GCD(long long a, long long b) { return (b == 0) ? a : GCD(b, a % b); }
inline long long LCM(long long a, long long b) { return a / GCD(a, b) * b; }
struct GCD_type {
  long long x, y, d;
};
GCD_type ex_GCD(long long a, long long b) {
  if (b == 0) return {1, 0, a};
  GCD_type pom = ex_GCD(b, a % b);
  return {pom.y, pom.x - a / b * pom.y, pom.d};
}
long long normalize(long long x, long long y) { return (x % y + y) % y; }
int main() {
  long long n1, a1, n2, a2, l, r;
  cin >> n1 >> a1 >> n2 >> a2 >> l >> r;
  GCD_type g = ex_GCD(n1, n2);
  if ((a2 - a1) % g.d != 0) return cout << 0, 0;
  long long lcm = LCM(n1, n2);
  long long tmp = (((g.x * (a2 - a1) / g.d) % (n2 / g.d)) % lcm) * n1;
  long long x = (a1 + tmp % lcm) % lcm;
  l = max(l, max(a1, a2));
  long long lr = normalize(l, lcm), xr = normalize(x, lcm);
  if (lr < xr)
    l += (xr - lr);
  else if (lr > xr)
    l += (lcm - lr + xr);
  if (l > r)
    cout << 0;
  else
    cout << (r - l) / lcm + 1;
  return 0;
}

### Prompt

Please provide a Cpp coded solution 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 GCD(long long a, long long b) { return (b == 0) ? a : GCD(b, a % b); }
inline long long LCM(long long a, long long b) { return a / GCD(a, b) * b; }
struct GCD_type {
  long long x, y, d;
};
GCD_type ex_GCD(long long a, long long b) {
  if (b == 0) return {1, 0, a};
  GCD_type pom = ex_GCD(b, a % b);
  return {pom.y, pom.x - a / b * pom.y, pom.d};
}
long long normalize(long long x, long long y) { return (x % y + y) % y; }
int main() {
  long long n1, a1, n2, a2, l, r;
  cin >> n1 >> a1 >> n2 >> a2 >> l >> r;
  GCD_type g = ex_GCD(n1, n2);
  if ((a2 - a1) % g.d != 0) return cout << 0, 0;
  long long lcm = LCM(n1, n2);
  long long tmp = (((g.x * (a2 - a1) / g.d) % (n2 / g.d)) % lcm) * n1;
  long long x = (a1 + tmp % lcm) % lcm;
  l = max(l, max(a1, a2));
  long long lr = normalize(l, lcm), xr = normalize(x, lcm);
  if (lr < xr)
    l += (xr - lr);
  else if (lr > xr)
    l += (lcm - lr + xr);
  if (l > r)
    cout << 0;
  else
    cout << (r - l) / lcm + 1;
  return 0;
}

```