516

#include <iostream>
#include <math.h>
#include <vector>
#include <map>
#include <sstream>

using namespace std;

struct NODE{
       int cnt;
       //map<int,int> freq;
       vector<int> num;
       int freq[35];
}node[33000];
int prime[33000];
vector<int> v;

stringstream s;

int _pow(int a,int p)
{
    if(p==0)
    return 1;
    return a*_pow(a,p-1);
}

int factorize()
{
    int tmp,index;
    int prev=-1;
    int counter=0;
    for(int i=3;i<33000;i++)
    {
       prev=-1;
       counter=0;
       if(prime[i]==0 && i%2!=0)
       {
           if(prev==i)
           {
             node[i].freq[counter-1]++;
           }
           else
           {
               prev=i;
               node[i].freq[counter++]++;
               node[i].num.push_back(prev);
           }
           //node[i].freq[i]++;
           continue;
       }
       tmp=i;
       index=0;
       while(tmp>=(v[index]*v[index]))
       {
           if(tmp%v[index]==0)
           {
              tmp/=v[index];
              if(prev==v[index])
              {
                 node[i].freq[counter-1]++;
              }
              else
              {
                  prev = v[index];
                  node[i].freq[counter++]++;
                  node[i].num.push_back(prev);
              }
              //node[i].freq[v[index]]++;
              index=-1;
           }
           index+=1;
       }
       if(tmp>1)
       {
          if(prev==tmp)
          {
             node[i].freq[counter-1]++;
          }
          else
          {
              prev=tmp;
              node[i].freq[counter++]++;
              node[i].num.push_back(prev);
          }

          //node[i].freq[tmp]++;
       }
       node[i].cnt=counter;
    }

   return 0;
}
int main()
{
    string str;
    double p = sqrt(33000)+4;

    for(int i=3;i<p;i+=2)
    {
        if(prime[i]==0)
        {
            for(int j=i+i;j<33000;j+=i)
            prime[j]=1;

        }
    }
    v.clear();
    v.push_back(2);

    for(int j=3;j<33000;j++)
    {
       if(prime[j]==0 && j%2!=0)
       v.push_back(j);
    }

    factorize();
    int n,numb;
    int a,b;
    while(1)
    {
       getline(cin,str);
       if(str=="0")
       break;
       istringstream s(str);
       int c=0;
       numb=1;
       while(s>>n)
       {
         if(c==0)
         {
            a=n;
            c=1;
         }
         else if(c)
         {
            b=n;
            c=0;

            numb*=_pow(a,b);
         }
       }
       NODE tNode = node[numb-1];
       //cout<<tNode.num.size()<<"\n";
       //cout<<tNode.num[5]<<" "<<tNode.freq[5]<<"\n";
       //for(int i=node[numb-1].num.size()-1;i>=0;i++)
       for(int i=(tNode.num.size()-1);i>=0;i--)
       {
          cout<<tNode.num[i]<<" ";//cout<<ii->first<<" "<<ii->second<<" ";
          if(i)
          cout<<tNode.freq[i]<<" ";
          else
          cout<<tNode.freq[i]<<"\n";

       }
    }

    return 0;
}