Two little greedy bears have found two pieces of cheese in the forest of weight a and b grams, correspondingly. The bears are so greedy that they are ready to fight for the larger piece. That's where the fox comes in and starts the dialog: "Little bears, wait a little, I want to make your pieces equal" "Come off it fox, how are you going to do that?", the curious bears asked. "It's easy", said the fox. "If the mass of a certain piece is divisible by two, then I can eat exactly a half of the piece. If the mass of a certain piece is divisible by three, then I can eat exactly two-thirds, and if the mass is divisible by five, then I can eat four-fifths. I'll eat a little here and there and make the pieces equal". 

The little bears realize that the fox's proposal contains a catch. But at the same time they realize that they can not make the two pieces equal themselves. So they agreed to her proposal, but on one condition: the fox should make the pieces equal as quickly as possible. Find the minimum number of operations the fox needs to make pieces equal.


-----Input-----

The first line contains two space-separated integers a and b (1 ≤ a, b ≤ 10^9). 


-----Output-----

If the fox is lying to the little bears and it is impossible to make the pieces equal, print -1. Otherwise, print the required minimum number of operations. If the pieces of the cheese are initially equal, the required number is 0.


-----Examples-----
Input
15 20

Output
3

Input
14 8

Output
-1

Input
6 6

Output
0

Difficulty: interview

Starter code:

Solutions:
a,b=list(map(int,input().split()))
def gcd(a,b):
    if(b==0):
        return a
    return gcd(b,a%b)
def burn(n):
    c=0
    while(n%2==0):
        c+=1
        n=n//2
    while(n%3==0):
        c+=1
        n=n//3
    while(n%5==0):
        c+=1
        n=n//5
    return [c,n]
if(a==b):
    print(0)
else:
    g=gcd(a,b)
    c=a//g
    d=b//g
    l1=burn(c)
    l2=burn(d)
    if(l1[1]==1 and l2[1]==1):
        print(l1[0]+l2[0])
    else:
        print(-1)


from math import *

[n, k] = [int(i) for i in input().split()]
arr = [[0 for i in range(6)] for j in range(2)]
for i in [2, 3, 5]:
    while n % i == 0:
        n /= i
        arr[0][i] += 1
for i in [2, 3, 5]:
    while k % i == 0:
        k /= i
        arr[1][i] += 1
  
if n != k:
    print(-1)
else:
    r = abs(arr[1][5] - arr[0][5])
    r += abs(arr[1][3] - arr[0][3])
    r += abs(arr[1][2] - arr[0][2])
    print(r)


from fractions import gcd
a,b = map(int,input().split())
if a==b:
    print(0)
    return
c =  gcd(a, b)
div1 = dict()
div2 = dict()
a1 = a
b1 = b
c1 = c
for i in [2,3,5]:
    div1[i]=0
    while a1%i==0:
        div1[i]+=1
        a1//=i
    div2[i]=0
    while b1%i==0:
        div2[i]+=1
        b1//=i
ans = 0
for i in [2,3,5]:
    while div1[i]!=div2[i]:
        if div1[i]>div2[i]:
            a//=i
            ans+=1
            div1[i]-=1
        else:
            b//=i
            ans+=1
            div2[i]-=1
if a!=b:
    print(-1)
else:
    print(ans)

import math
import fractions
a,b=list(map(int,input().split()))
a2=0
a3=0
a5=0
b2=0
b3=0
b5=0
while a%2==0:
    a=a/2
    a2=a2+1
while a%3==0:
    a=a/3
    a3=a3+1
while a%5==0:
    a=a/5
    a5=a5+1
while b%2==0:
    b=b/2
    b2=b2+1
while b%3==0:
    b=b/3
    b3=b3+1
while b%5==0:
    b=b/5
    b5=b5+1
if a!=b:print(-1)
else:
    print(math.ceil(math.fabs(b2-a2)+math.fabs(b5-a5)+math.fabs(b3-a3)))


a, b = map(int, input().split())
k = a
l = b
a2, a3, a5 = 0, 0, 0
b2, b3, b5 = 0, 0, 0
while k : 
    if k % 2 == 0 :
        a2 += 1
        k = k / 2
    elif k % 3 == 0 :
        a3 += 1
        k = k / 3
    elif k % 5 == 0 :
        a5 += 1
        k = k / 5
    else : break
     
while l : 
    if l % 2 == 0 :
        b2 += 1
        l = l / 2
    elif l % 3 == 0 :
        b3 += 1
        l = l / 3
    elif l % 5 == 0 :
        b5 += 1
        l = l / 5
    else : break
if k != l :
    print(-1)
else :
    print(max(a2, b2) - min(a2, b2) + max(a3, b3) - min(a3, b3) + max(a5, b5) - min(a5, b5))

import sys
#sys.stdin = open('prefrev.in', 'r')
#sys.stdout = open('prefrev.out', 'w')
n, m = map(int, input().split())
divs=[2,3,5]
ar=[0]*6
br=[0]*6
tn=n; tm=m
for i in divs:    
    while tn % i == 0 and tn > 0:
        ar[i] += 1
        tn //= i
    while tm % i == 0 and tm > 0:
        br[i] += 1
        tm //= i
print
if tn != tm:
    print('-1')
else:
    #print('ok')
    ans = 2e9
    for i in range(min(br[2], ar[2])+1):
        for j in range(min(br[3], ar[3])+1):
            for k in range(min(br[5],ar[5])+1):
                if ar[2]-i+br[2]-i+ar[3]-j+br[3]-j+ar[5]-k+br[5]-k<ans:
                    ans=ar[2]-i+br[2]-i+ar[3]-j+br[3]-j+ar[5]-k+br[5]-k
    print(ans)                

3

def readln(): return tuple(map(int, input().split()))

mem = dict()

def calc(a, b):
    if a == b:
        return 0
    if (a, b) in mem:
        return mem[(a, b)]
    var = [2**30]
    if a % 2 == 0:
        var.append(calc(a // 2, b))
    if a % 3 == 0:
        var.append(calc(a // 3, b))
    if a % 5 == 0:
        var.append(calc(a // 5, b))
    if b % 2 == 0:
        var.append(calc(a, b // 2))
    if b % 3 == 0:
        var.append(calc(a, b // 3))
    if b % 5 == 0:
        var.append(calc(a, b // 5))
    mem[(a, b)] = min(var) + (min(var) < 2**30)
    return mem[(a, b)]

a, b = readln()
res = calc(a, b)
print(-1 if res == 2**30 else res)


import math
from fractions import gcd

def primes(limit):
    Ans=[]
    C=[True]*(limit+1)
    L=list(range(2,limit+1))
    for item in L:
        if(C[item]):
            i=2
            while(item*i<=limit):
                C[item*i]=False
                i+=1
    for item in L:
        if(C[item]):
            Ans+=[item]
    return Ans


a,b=list(map(int,input().split()))
aa=a
bb=b
A=[]
B=[]

p=primes(int(math.sqrt(10**9)))

for i in range(len(p)):
    if(p[i]>a):
        break
    while(a%p[i]==0):
        A.append(p[i])
        a//=p[i]
if(a!=1):
    A.append(a)


for i in range(len(p)):
    if(p[i]>b):
        break
    while(b%p[i]==0):
        B.append(p[i])
        b//=p[i]
if(b!=1):
    B.append(b)

if(aa==1 and bb==1):
    print(0)

elif(aa==1):
    Done=True
    for item in B:
        if(item>5):
            Done=False
            break
    if(Done):
        print(len(B))
    else:
        print(-1)
elif(bb==1):
    Done=True
    for item in A:
        if(item>5):
            Done=False
            break
    if(Done):
        print(len(A))
    else:
        print(-1)

else:

    B.sort()
    A.sort()
    Done=True
    ind=0
    ans=0
    while(A!=B):
        if(ind>=len(A) and ind>=len(B)):
            Done=False
            break
        elif(ind>=len(A)):
            if(B[-1]>5):
                Done=False
                break
            else:
                ans+=len(B)-ind
                break
        elif(ind>=len(B)):
            if(A[-1]>5):
                Done=False
                break
            else:
                ans+=len(A)-ind
                break
        if(A[ind]==B[ind]):
            ind+=1
            continue
        
        if(A[ind]<B[ind]):
            if(A[ind]>5):
                Done=False
                break
            else:
                ans+=1
                A.pop(ind)
        else:
            if(B[ind]>5):
                Done=False
                break
            else:
                ans+=1
                B.pop(ind)
    if(Done):
        print(ans)
    else:
        print(-1)

        


def gcd(a, b): return gcd(b, a % b) if b else a
a, b = map(int, input().split())
k = 2 ** 30 * 3 ** 19 * 5 ** 13
u, v = gcd(k, a), gcd(k, b)
if a * v != b * u: print(-1)
else:
    s, c = 0, u * v // (gcd(u, v) ** 2)
    for i in [2, 3, 5]:
        while c % i == 0:
            c //= i
            s += 1
    print(s)

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

def gcd(a, b):
    if a > b:
        a, b = b, a
    while True:
        t = b % a
        if t == 0:
            return a
        a, b = t, a
    return 1

a, b = map(int, input().split())
g = gcd(a, b)
m = a/g * b/g
n = 0
while m % 2 == 0:
    m /= 2
    n += 1
while m % 3 == 0:
    m /= 3
    n += 1
while m % 5 == 0:
    m /= 5
    n += 1
print(n if m == 1 else -1)

a, b = map(int, input().split())
x = y = z = 0
while a % 2 == 0:
  x += 1
  a //= 2
while a % 3 == 0:
  y += 1
  a //= 3
while a % 5 == 0:
  z += 1
  a //= 5
while b % 2 == 0:
  x -= 1
  b //= 2
while b % 3 == 0:
  y -= 1
  b //= 3
while b % 5 == 0:
  z -= 1
  b //= 5
print(abs(x) + abs(y) + abs(z) if a == b else -1)

a, b = list(map(int, input().split()))
res = 0

for x in (2, 3, 5):
	while a % x == 0 and b % x == 0:
		a //= x
		b //= x
	while a % x == 0:
		a //= x
		res += 1
	while b % x == 0:
		b //= x
		res += 1

if a == b:
	print(res)
else:
	print(-1)


def d(q,d):
	c=0
	while q%d == 0:
		q//=d
		c+=1
		pass
	return (c,q)
	pass

def main():
	a2=0
	a3=0
	a5=0
	b2=0
	b3=0
	b5=0
	a,b=map(int,input().split(" "))
	if a == b:
		print (0)
		return
		pass
	at,bt=a,b
	a2,a=d(a,2)
	a3,a=d(a,3)
	a5,a=d(a,5)
	b2,b=d(b,2)
	b3,b=d(b,3)
	b5,b=d(b,5)
	if a != b:
		print (-1)
		return
		pass
	print (abs(a2-b2)+abs(a3-b3)+abs(a5-b5))
	pass

main()

import math
import fractions

def pFactors(n):
        """Finds the prime factors of 'n'"""
        from math import sqrt
        pFact, limit, check, num = [], int(sqrt(n)) + 1, 2, n
        if n == 1: return []
        for check in range(2, limit):
             while num % check == 0:
                pFact.append(check)
                num /= check
        if num > 1:
          pFact.append(num)
        return pFact

def solve():
    a , b = map(int, input().split())
    if a == b:
        print(0)
        return
    gcd = fractions.gcd(a, b)
    af = pFactors(a//gcd)
    bf = pFactors(b//gcd)
    res = 0
    for val in af:
        if val == 2 or val == 3 or val == 5:
            res+=1
        else:
            print(-1)
            return
    for val in bf:
        if val == 2 or val == 3 or val == 5:
            res+=1
        else:
            print(-1)
            return
    ares = gcd
    for val in af:
        ares *= val
    bres = gcd
    for val in bf:
        bres *= val
    if ares != a or bres != b:
        #print(ares, bres)
        print(-1)
        return
    print(res)


solve()

from fractions import gcd
def o(n):
    v = 0
    for f in (2, 3, 5):
        while n % f == 0:
            n //= f
            v += 1
    return v if n == 1 else -1
a, b = map(int, input().split())
f = gcd(a, b)
v1, v2 = o(a // f), o(b // f)
print(v1 + v2 if v1 >= 0 and v2 >= 0 else -1)

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

def main():
    a, b = list(map(int, input().split(' ')))
    gg = gcd(a, b)
    ans = 0
    can = 1
    A = []
    A.append(a / gg)
    A.append(b / gg)
    for g in A:
        while(g != 1):
            ok = 0
            if g % 2 == 0:
                g = g / 2
                ok = 1
                ans = ans + 1
            if g % 3 == 0:
                g = g / 3
                ok = 1
                ans = ans + 1
            if g % 5 == 0:
                g = g / 5
                ok = 1
                ans = ans + 1
            if ok == 0:
                can = 0
                break
    
    if can == 0:
        print("-1")
    else:
        print(ans)

def __starting_point():
    main()

__starting_point()

def main():
    from math import gcd
    a, b = list(map(int, input().split()))
    g, res = gcd(a, b), 0
    for x in a // g, b // g:
        for p in 2, 3, 5:
            while not x % p:
                x //= p
                res += 1
        if x != 1:
            print(-1)
            return
    print(res)


def __starting_point():
    main()

__starting_point()

def scan(type):
    return list(map(type, input().split()))

a, b = scan(int)

a2 = a3 = a5 = b2 = b3 = b5 = 0

while a%2 == 0:
    a /= 2
    a2 += 1
while a%3 == 0:
    a /= 3
    a3 += 1
while a%5 == 0:
    a /= 5
    a5 += 1

while b%2 == 0:
    b /= 2
    b2 += 1
while b%3 == 0:
    b /= 3
    b3 += 1
while b%5 == 0:
    b /= 5
    b5 += 1

ans = 0
if a != b:
    print(-1)
else:
    ans += max(a2,b2) - min(a2,b2)
    ans += max(a3,b3) - min(a3,b3)
    ans += max(a5,b5) - min(a5,b5)
    print(ans)







def scan(type):
    return list(map(type, input().split()))

a, b = scan(int)

a2 = a3 = a5 = b2 = b3 = b5 = 0

while a%2 == 0:
    a /= 2
    a2 += 1
while a%3 == 0:
    a /= 3
    a3 += 1
while a%5 == 0:
    a /= 5
    a5 += 1

while b%2 == 0:
    b /= 2
    b2 += 1
while b%3 == 0:
    b /= 3
    b3 += 1
while b%5 == 0:
    b /= 5
    b5 += 1

ans = 0
if a != b:
    print(-1)
else:
    ans += max(a2,b2) - min(a2,b2)
    ans += max(a3,b3) - min(a3,b3)
    ans += max(a5,b5) - min(a5,b5)
    print(ans)






# 1482718805944


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

a2=0
a3=0
a5=0
b2=0
b3=0
b5=0

while a%2==0:
    a//=2
    a2+=1
while a%3==0:
    a//=3
    a3+=1
while a%5==0:
    a//=5
    a5+=1
while b%2==0:
    b//=2
    b2+=1
while b%3==0:
    b//=3
    b3+=1
while b%5==0:
    b//=5
    b5+=1

tot=max(a2-min(a2,b2),b2-min(a2,b2))+max(a3-min(a3,b3),b3-min(a3,b3))+max(a5-min(a5,b5),b5-min(a5,b5))
if a==b:
    print(tot)
else:print(-1)


import math
a, b = map(int, input().split())
c = math.gcd(a, b)
a //= c
b //= c
ans = 0
def d(x, t):
    nonlocal ans
    while(x > 1 and x % t == 0):
        x //= t
        ans += 1
    return x
for i in [2, 3, 5]:
    a = d(a, i)
    b = d(b, i)
print([-1, ans][a == 1 and b == 1])

a,b=map(int,input().split())
if a==b :
    print(0)
    return
a1,a3,a5,b1,b3,b5=0,0,0,0,0,0

while a!=0 :
    if a%2==0 : a,a1= a/2 ,a1+1
    elif a%3==0 :   a,a3= a/3 ,a3+1
    elif a%5==0 : a,a5= a/5 ,a5+1
    else :  break
while b!=0 :
    if b%2==0 :     b,b1= b/2 ,b1+1
    elif b%3==0 :   b,b3= b/3 ,b3+1
    elif b%5==0 :   b,b5= b/5 ,b5+1
    else :  break
if a!=b : print(-1)
else : print(abs(a1-b1) + abs(a3-b3) + abs(a5-b5))

a, b = map(int, input().split())
res = 0

for x in (2, 3, 5):
	while a % x == 0 and b % x == 0:
		a //= x
		b //= x
	while a % x == 0:
		a //= x
		res += 1
	while b % x == 0:
		b //= x
		res += 1

if a == b:
	print(res)
else:
	print(-1)

from math import gcd
a, b = map(int, input().split())
g, ans = gcd(a, b), 0
a, b = a // g, b // g
while a % 2 == 0:
  a //= 2
  ans += 1
while a % 3 == 0:
  a //= 3
  ans += 1
while a % 5 == 0:
  a //= 5
  ans += 1
while b % 2 == 0:
  b //= 2
  ans += 1
while b % 3 == 0:
  b //= 3
  ans += 1
while b % 5 == 0:
  b //= 5
  ans += 1
print(-1 if a != 1 or b != 1 else ans)

MAX = 1e9 + 7
m = {}
def main():
    nonlocal m
    def f(a, b):
        if (a, b) in m:
            return m[(a, b)]
        if a == b:
            return 0
        if a < 0 or b < 0:
            return int(MAX)
        if a < b:
            return f(b, a)
        ret = int(MAX)
        if a % 2 == 0:
            ret = min(ret, 1 + f(a/2, b))
        if a % 3 == 0:
            ret = min(ret, 1 + f(a/3, b))
        if a % 5 == 0:
            ret = min(ret, 1 + f(a/5, b))
        m[(a, b)] = ret
        return ret
    (a, b) = list(map(int, input().split(' ')))
    x = f(a, b)
    if x == MAX:
        return -1
    return x

print(main())