# 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}")