#include<iostream>
using namespace std;
int main ()
{
    int n, f, putere;
    cin>>n;
    f=2;
    while(n>1)
    {
        putere=0;
        while(n%f==0)
        {
            putere++;
            n/=f;
        }
        if(putere!=0)
            cout<<f<<" "<<putere<<endl;
        if(f==2)
            f++;
        else f+=2;
        if(f*f>n && n!=1)
        {
            cout<<n<<" "<<1;
            n=1;
        }
    }
}