> RT

//#include <bits/stdc++.h>
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <cmath>
using namespace std;

#define INF 0x3f3f3f3f
#define pb push_back
#define abs(a) (a)>0?(a):-(a)
#define min(a,b) (a)>(b)?(a):(b)
#define lalal puts("*******")
typedef long long int LL ;
/*******************************/

const int MOD = 10086;
const int N = 32768;

int prime[32768],kp;
int Is_or[32768];

void shacker()
{
    memset(Is_or,1,sizeof(Is_or));
    kp=0;
    for(int i=2;i<N;i++)
    {
        if(Is_or[i]) prime[kp++]=i;
        for(int j=0;j<kp&&i*prime[j]<N;j++)
        {
            Is_or[i*prime[j]]=0;
            if(0==i%prime[j]) break;
        }
    }
    //printf("%d\n",kp);
    return ;
}

char a[101010];
int  b[101010];
int  c[101010];
int main()
{
    shacker();

    while( 1 )
    {
        gets(a);
        int len = strlen (a);
        int num =0,tem=0;
        a[len]=' ';
        for(int i=0;i<=len;i++)
        {
            if(a[i]!=' ')    tem=tem*10+a[i]-'0';
            else             b[num++]=tem, tem=0;
        }
        if(num==1&&b[0]==0) break;
        
        int n=1;
        for(int i=0;i<num;i+=2)
            for(int j=0;j<b[i+1];j++)
                n*=b[i];
        
        n--;
        num=0;
        int flag=0;
        for(int i=0;i<kp&&n>=prime[i];i++)
        {
            c[i]=0;
            while(n%prime[i]==0)  n/=prime[i],c[i]++;
        }

        for(int i=kp-1;i>=0;i--)
        {
            if(c[i])
            {
                if(flag) printf(" ");
                printf("%d %d",prime[i],c[i]),flag=1;
            }
        }
        puts("");
    }
    return 0;
}

/***************************/
超时我都认  为什么输出超限啊。。