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
#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    long long n,m;
         cin>>n;
   m=sqrt(n);
   cout<<n<<":";
    for(int i=2;i<=n;i++)
     {
      while(n%i==0){
        cout<<" "<<i;
        n/=i;
         }
   if(n==1)
     break;
      if(i>=sqrt(n))
        {
        cout<<" "<<n;
        break;
        }
}
    cout<<endl;
}