/*   @JUDGE_ID:   1705PZ   516   C */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main()
{
	int i,j,loop,count,top = 42,top1,first = 1;
	long ans,m,n;
	char string[513],temp[513];
	long answer[3600][2];
	long prime[3600] = {  2,  3,  5,  7, 11, 13, 17, 19, 23, 29,
			     31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
			     73, 79, 83, 89, 97,101,103,107,109,113,
			    127,131,137,139,149,151,157,163,167,173,
			    179,181};

	for(m = 183;m <= 32768;m++)
	{
		count = 0;
		for(i = 0;i < 42;i++)
		{
			if(m % prime[i] == 0)
			{
				count++;
				break;
			}
		}
		if(count == 0)
			prime[top++] = m;
	}

	for(i = 0;i < 3600;i++)
	{
		answer[i][0] = 0;
		answer[i][1] = 0;
	}

	while(1)
	{
		gets(string);
		if(string[0] == '0')
			break;

		i = 0;
		ans = 1;
		loop = 1;
		top1 = 0;
		while(loop)
		{
			for(j = 0;;i++,j++)
			{
				temp[j] = string[i];
				if(string[i] == ' ')
				{
					i++;
					temp[j] = 0;
					break;
				}
			}
			m = atol(temp);

			for(j = 0;;i++,j++)
			{
				temp[j] = string[i];
				if(string[i] == ' ' || string[i] == 0)
				{
					temp[j] = 0;
					if(string[i] == 0)
						loop = 0;
					i++;
					break;
				}
			}
			n = atol(temp);

			ans *= pow(m,n);
		}

		ans -= 1;

		while(ans != 1)
		{
			for(i = 0;i < top;i++)
			{
				if(ans % prime[i] == 0)
				{
					count = 0;
					for(j = 0;j < top1;j++)
					{
						if(answer[j][0] == prime[i])
						{
							answer[j][1]++;
							count++;
							break;
						}
					}

					if(count == 0)
					{
						answer[top1][0] = prime[i];
						answer[top1][1] = 1;
						top1++;
					}
					ans /= prime[i];
					break;
				}
			}
		}

		if(first != 1)
			printf("\n");
		first = 0;

		for(i = top1 - 1;i >= 0;i--)
			printf("%ld %ld ",answer[i][0],answer[i][1]);
	}
	return 0;
}
@END_OF_SOURCE_CODE