#include<stdio.h>
#include<math.h>

#define ll long long

int A[100];
int B[100];
int P;
int Q;
int nr;
ll MAX;
int a;

void descompunere(void)
{
	int a = sqrt(P);
	for(int i=2;i<=a && P != 1;i++)
		if(P%i == 0)
		{
			A[++nr] = i;
			while(P % i == 0)
			{
				P /= i;
				B[nr] ++;
			}
		}
	if(P != 1)
	{
		A[++nr] = P;
		B[nr] = 1;
	}
	for(int i=1;i<=nr;i++)
		B[i] *= Q;
}

int ciur(void)
{
	for(int i=1;i<=nr;i++)
	{
		ll j=A[i];
		for(;B[i] > 0;j+=A[i])
		{
			ll a = j;
			while(a%A[i] == 0)
			{
				a /= A[i];
				-- B[i];
			}
		}
		j -= A[i];
		if(j>MAX)
			MAX = (ll)j;
	}
}

int main()
{
	FILE *f = fopen("gfact.in","r");
	FILE *g = fopen("gfact.out","w");
	
	fscanf(f,"%d %d",&P,&Q);
	descompunere();
	for(int i=1;i<=nr;i++)
		printf("%d %d\n",A[i],B[i]);
	ciur();
	fprintf(g,"%llu",MAX);

	
	fclose(g);
	fclose(f);
	return 0;
}