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.
The first line contains two space-separated integers *a* and *b* (1 ≤ *a*, *b* ≤ 10<sup class="upper-index">9</sup>).
from collections import deque
from math import gcd

def has_valid_prime_factors(n):
    for prime in [2, 3, 5]:
        while n % prime == 0:
            n //= prime
    return n == 1

def bfs(a, b):
    # Check if it's impossible to make a and b equal
    if not (has_valid_prime_factors(gcd(a, b))):
        return -1
    
    visited = set()
    queue = deque([(a, b, 0)])  # (weight_a, weight_b, steps)
    
    while queue:
        a, b, steps = queue.popleft()
        
        if a == b:
            return steps
        
        if (a, b) in visited:
            continue
        
        visited.add((a, b))
        
        # Apply operations
        for divisor, fraction in [(2, 1/2), (3, 2/3), (5, 4/5)]:
            if a % divisor == 0:
                new_a = int(a * fraction)
                queue.append((new_a, b, steps + 1))
            if b % divisor == 0:
                new_b = int(b * fraction)
                queue.append((a, new_b, steps + 1))

# Example usage
a = 14
b = 8
result = bfs(a, b)
if result == -1:
    print("It's impossible to make the pieces equal.")
else:
    print("Minimum number of operations:", result)
