p02467 Prime Factorize_32113
Factorize a given integer n.

Constraints

* 2 ≤ n ≤ 109

Input


n


An integer n is given in a line.

Output

Print the given integer n and :. Then, print prime factors in ascending order. If n is divisible by a prime factor several times, the prime factor should be printed according to the number of times. Print a space before each prime factor.

Examples

Input

12


Output

12: 2 2 3


Input

126


Output

126: 2 3 3 7
def primefactor(x):
    fac=[]
    for i in xrange(2,int(x**0.5)+1):
        while x%i==0:
            fac+=[i]
            x=x/i
    if x!=1:
        fac+=[x]
    return fac

n=input()
ans=primefactor(n)
print(str(n)+":"+" "+" ".join(map(str,ans)))