#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define mxn 1000000



bool mark[mxn+5]={false};
ll isprime[mxn+5],psize=0;




void sieve()
{
    mark[0]=true;
    mark[1]=true;

    ll i,j,k;
    for(i=2;i*i<=mxn;i++)
    {
    	if(mark[i]==false)
    	{
    		for(j=i*i;j<=mxn;j+=i)
    			mark[j]=true;
    	}
    }
    isprime[psize++]=2;
    for(i=3;i<=mxn;i+=2)
    {
    	if(mark[i]==false)
    		isprime[psize++]=i;
    }
}

ll con(string s)
{
	ll i,j,k,num=0;
	for(i=0;i<s.size();i++)
	{
		num=(num*10)+(s[i]-'0');
	}
//	cout<<"num "<<num<<endl;
	return num;
}


ll arrp[mxn+5],arre[mxn+5],ii=0,jj=0;


void convert(string s)
{
	ll i,j,k,num;
	string x="";
	ll cnt=1;
	for(i=0;i<s.size();i++)
	{
		if(s[i]==' ')
		{
            num=con(x);
            if(cnt%2==0)
               arre[jj++]=num;
           else
           	arrp[ii++]=num;
           cnt++;
            x="";
		}
		else
		{
			x+=s[i];
		}
	}
	arre[jj++]=con(x);
}


ll makenum()
{
	ll i,j,k,n=1,x;
	for(i=0;i<ii;i++)
	{
		x=pow(arrp[i],arre[i])+0.00000001;
		n*=x;
	}
	return n;
}

vector<ll>ans,cnt;


void primefact(ll n)
{
	ll i,j,k,c=0;
	ans.clear();
	cnt.clear();
	for(i=0;isprime[i]*isprime[i]<=n && i<psize;i++)
	{
		c=0;
		if(n%isprime[i]==0)
		{
             while(n%isprime[i]==0)
             {
             	c++;
             	n/=isprime[i];
             }
		ans.push_back(isprime[i]);
		cnt.push_back(c);
	}
	}
	if(n>1)
	{
		ans.push_back(n);
		cnt.push_back(1);
	}

	for(i=ans.size()-1;i>=0;i--)
	{
		if(i==ans.size()-1)
			cout<<ans[i]<<" "<<cnt[i];
		else
        cout<<" "<<ans[i]<<" "<<cnt[i];
	}
	cout<<endl;
}



int main()
{
	freopen("input.txt","r",stdin);
	freopen("out.txt","w",stdout);
    sieve();
	string s;
	ll i,j,k;
    while(getline(cin,s))
    {
    	if(s=="0" && s.size()==1)
    		break;
         
    	memset(arre,0,sizeof(arre));
    	memset(arrp,0,sizeof(arrp));
    	ii=0,jj=0;
       convert(s);
       ll n=makenum();
       n-=1;
       primefact(n);
    }
}