Iahub and his friend Floyd have started painting a wall. Iahub is painting the wall red and Floyd is painting it pink. You can consider the wall being made of a very large number of bricks, numbered 1, 2, 3 and so on. 

Iahub has the following scheme of painting: he skips x - 1 consecutive bricks, then he paints the x-th one. That is, he'll paint bricks x, 2·x, 3·x and so on red. Similarly, Floyd skips y - 1 consecutive bricks, then he paints the y-th one. Hence he'll paint bricks y, 2·y, 3·y and so on pink.

After painting the wall all day, the boys observed that some bricks are painted both red and pink. Iahub has a lucky number a and Floyd has a lucky number b. Boys wonder how many bricks numbered no less than a and no greater than b are painted both red and pink. This is exactly your task: compute and print the answer to the question. 


-----Input-----

The input will have a single line containing four integers in this order: x, y, a, b. (1 ≤ x, y ≤ 1000, 1 ≤ a, b ≤ 2·10^9, a ≤ b).


-----Output-----

Output a single integer — the number of bricks numbered no less than a and no greater than b that are painted both red and pink.


-----Examples-----
Input
2 3 6 18

Output
3


-----Note-----

Let's look at the bricks from a to b (a = 6, b = 18). The bricks colored in red are numbered 6, 8, 10, 12, 14, 16, 18. The bricks colored in pink are numbered 6, 9, 12, 15, 18. The bricks colored in both red and pink are numbered with 6, 12 and 18.

Difficulty: interview

Starter code:

Solutions:
import fractions

x, y, a, b = list(map(int, input().split()))
d = fractions.gcd(x, y)
d = x * y // d
print(b // d - (a - 1) // d)


import math
import sys
from fractions import gcd

x,y,a,b=list(map(int,sys.stdin.readline().split()))

g=(x*y)//gcd(x,y)

s=math.ceil(a/g)

e=math.floor(b/g)

print(e-s+1)



x, y, a, b = list(map(int, input().split()))

def arch(a, b):
    while b != 0:
        a, b = b, a % b
    return a

c = x * y // arch(x, y)
print(b // c - (a - 1) // c)


from fractions import *
x,y,a,b = list(map(int,input().split()))
nok = (x*y)//gcd(x,y)
first = (a // nok) * nok + (nok if a%nok != 0 else 0)
second = (b//nok) * nok
if first > b:
    print(0)
else:
    print((second-first)//nok +(1 if second % nok == 0 else 0))



def gcd(x,y):
    if y%x==0:
        return x
    else:
        return gcd(y%x,x)


def __starting_point():
    inp = input()
    arr = inp.split(' ')
    x = int(arr[0])
    y = int(arr[1])
    a = int(arr[2])
    b = int(arr[3])
    g = gcd(min(x,y),max(x,y))
    l = (x*y)//g
    i = 0
    for i in range(a,a+l+1):
        if i > b:
            break
        if i%l==0:
            break
    ans = 0
    if b>=i:
        ans=(b-i)//l + 1
    print(ans)

__starting_point()

def gcd(a,b) :
    return a if b==0 else gcd(b,a%b)

def lcm(a,b) : return a/gcd(a,b)*b

t = input().split(' ')
x,y,a,b = (int(i) for i in t)
l = lcm(x,y)
print(int(b//l-(a-1)//l+0.5))


from fractions import gcd


def nok(a, b):
    return a * b // gcd(a, b)


x, y, a, b = list(map(int, input().split()))
lcs = nok(x, y)
l = lcs - a % lcs + a if a % lcs != 0 else a
# print(l)
ans = (b - l) // lcs + 1
print(ans)


from math import*

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)

x, y, a, b = list(map(int, input().split()))
nok = (x * y) // gcd(x, y)
a += (nok - a % nok) % nok
b -= b % nok
print((b - a) // nok + 1)

x, y, a, b = list(map(int, input().split()))
count = 0
A = 2 * [0]
for i in range(a, b + 1):
    if i % x == 0 and i % y == 0:
        A[count] = i
        count += 1
    if count == 2:
        break
if count == 2:
    RR = A[1] - A[0]
    print((b - A[0]) // RR + 1)
else:
    print(count)


def test(x,y,a,b):
    t=x*y//gcd(x,y)
    return (b//t - (a-1)//t)


def gcd(a,b):
    if a<b:
        a,b=b,a
    while b!=0:
        a,b=b,a%b
    return a

def main():
    s=input()
    s=list(map(int,s.split()))
    print(test(s[0],s[1],s[2],s[3]))

def __starting_point():
    main()

__starting_point()

from fractions import gcd
x, y, a, b = map(int,input().split())
nok = (x * y) // gcd(x, y)
xx = (a // nok) * nok
if a%nok != 0:
    xx += nok
yy= (b //nok) * nok
if xx > b:
    print(0)
else:
    if yy% nok == 0:
        f = 1
    else:
        f = 0
    print((yy-xx) // nok + f)

# for finding lcm we need to know gcd
def gcd(a,b):
    while b!=0:
        temp=b
        b=a%b
        a=temp
    return a
def lcm(a,b):
    g=gcd(a,b)
    lc=(a*b)//g
    return lc

while(1):
    try:
        a=list(map(int,input().split()))
        maxi=a[0] if a[0]>a[1] else a[1]
        if maxi==a[0]:
            mini=a[1]
         
        else:
            maxi=a[1]
            mini=a[0]
        l=lcm(maxi,mini)
        c=0
        maxi=a[2] if a[2]>a[3] else a[3]
        if maxi==a[2]:
            mini=a[3]
        else:
            maxi=a[3]
            mini=a[2]
        print(maxi//l-(mini-1)//l)
        
    except EOFError:
        break

            
            
        
        
        
        


from fractions import gcd

def lcd(a, b):
    g = gcd(a, b)
    return a*b//g

def __starting_point():
    x, y, a, b = [int(x) for x in input().split()]
    l = lcd(x, y)
    r = a%l
    if r == 0:
        print((b-a)//l+1)
    else:
        print((b-(a+(l-r)))//l+1)

__starting_point()

from fractions import gcd

def lcd(a, b):
    g = gcd(a, b)
    return a*b//g

def __starting_point():
    x, y, a, b = [int(x) for x in input().split()]
    l = lcd(x, y)
    print(b//l-(a-1)//l)

__starting_point()

x, y, a, b = (int(i) for i in input().split())

p = 1
for i in range(2, 1001):
	if x % i == 0 and y % i == 0:
		x = x // i
		y = y // i
		p *= i

print(b // (x * y * p) - (a - 1) // (x * y * p))

def GCD(a, b):
    while a % b != 0:
        a, b = b, a % b
    return b

def LCM(a, b):
    return a * b // GCD(a, b)

l = input().split(' ')
x, y, a, b = int(l[0]), int(l[1]), int(l[2]), int(l[3])
lcm = LCM(x, y)
print(b // lcm - (a - 1) // lcm)


import sys
import math
import fractions
f = sys.stdin

#f = open("input.txt", "r")

line_ = list(map(int, f.readline().split()))

line = []
for it in line_:
	line.append(it)

x = int(line[0])
y = int(line[1])
a = int(line[2])
b = int(line[3])
xy = x * y / fractions.gcd(x, y)
ans = b // xy - (a - 1) // xy
print( int(ans) )


def gcd (x, y):
    if x < y: x, y = y, x
    while x % y != 0:
        x, y = y, x % y
    return y

def lcm (x, y):
    return ((x * y) // gcd(x, y))

x, y, a, b = (int(i) for i in input().split(' '))

f = lcm(x, y)

k = (b // f) - ((a - 1) // f)

##if a % f == 0 or b % f == 0: k += 1

print(k)

from fractions import gcd
x, y, a, b = list(map(int, input().split()))
m = x // __import__("fractions").gcd(x, y) * y
f = (a // m) * m
if f < a: f += m
t = (b // m) * m
print(0 if t < f else 1 + (t - f) // m)


x,y,a,b = map(int, input().split())
g = 1
while g % x or g % y:
    g += 1
print(b // g - (a - 1) // g)

3

x, y, a, b = tuple(map(int, input().split()))

def gcd(i, j):
    while i:
        i, j = j % i, i
    return j

s = x * y // gcd(x, y)
print(b // s - (a - 1) // s)


# -*- coding: utf-8 -*-

def gcd(a, b):
    x, y = max(a, b), min(a, b)
    while x % y:
        x, y = y, x % y
    return y

def test():
    assert gcd(1071, 462) == 21
    assert gcd(462, 1071) == 21
    assert gcd(81, 135) == 27
    print("test passes")

def solve(x, y, a, b):
    tmp = x * y // gcd(x, y)
    #print(x, y, gcd(x, y))
    #print(b // tmp, a // tmp)
    return b // tmp - (a - 1) // tmp

x, y, a, b = list(map(int, input().split()))
print(solve(x, y, a, b))
    


import fractions
x,y,a,b=list(map(int,input().split()))
d=fractions.gcd(x,y)
d=x*y // d
print(b // d -(a-1)//d)


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def lcm(a, b):
    return a * b / gcd(a, b)

x, y, a, b = list(map(int, input().split(' ')))
l = lcm(x, y)
print(int(b // l - (a - 1) // l))


import fractions
x, y, a, b = map(int, input().split())
nok = x * y // fractions.gcd(x, y)
c = (a // nok) * nok
if c < a:
    c += nok
d = (b // nok) * nok
if d % nok == 0:
    d += nok
print((d - c) // nok)