# your code goes here
def prime_factors(n):
    factors = {}
 
    # Check for factor 2
    while n % 2 == 0:
        factors[2] = factors.get(2, 0) + 1
        n //= 2
 
    # Check for odd factors starting from 3
    i = 3
    while i * i <= n:
        while n % i == 0:
            factors[i] = factors.get(i, 0) + 1
            n //= i
        i += 2
 
    # If remaining n is a prime number greater than 2
    if n > 2:
        factors[n] = 1
 
    return factors
 
# Example usage
n = 18
for factor, count in prime_factors(n).items():
    print(f"{factor} {count}")

IyB5b3VyIGNvZGUgZ29lcyBoZXJlCmRlZiBwcmltZV9mYWN0b3JzKG4pOgogICAgZmFjdG9ycyA9IHt9CiAgICAKICAgICMgQ2hlY2sgZm9yIGZhY3RvciAyCiAgICB3aGlsZSBuICUgMiA9PSAwOgogICAgICAgIGZhY3RvcnNbMl0gPSBmYWN0b3JzLmdldCgyLCAwKSArIDEKICAgICAgICBuIC8vPSAyCiAgICAgICAgCiAgICAjIENoZWNrIGZvciBvZGQgZmFjdG9ycyBzdGFydGluZyBmcm9tIDMKICAgIGkgPSAzCiAgICB3aGlsZSBpICogaSA8PSBuOgogICAgICAgIHdoaWxlIG4gJSBpID09IDA6CiAgICAgICAgICAgIGZhY3RvcnNbaV0gPSBmYWN0b3JzLmdldChpLCAwKSArIDEKICAgICAgICAgICAgbiAvLz0gaQogICAgICAgIGkgKz0gMgogICAgICAgIAogICAgIyBJZiByZW1haW5pbmcgbiBpcyBhIHByaW1lIG51bWJlciBncmVhdGVyIHRoYW4gMgogICAgaWYgbiA+IDI6CiAgICAgICAgZmFjdG9yc1tuXSA9IDEKICAgICAgICAKICAgIHJldHVybiBmYWN0b3JzCgojIEV4YW1wbGUgdXNhZ2UKbiA9IDE4CmZvciBmYWN0b3IsIGNvdW50IGluIHByaW1lX2ZhY3RvcnMobikuaXRlbXMoKToKICAgIHByaW50KGYie2ZhY3Rvcn0ge2NvdW50fSIp