{首先，说明一个问题，一个数的大于它开方的质因数最多一个；等于的可以两个，即它开方得到的数是质数的话，即为该数；
问题可以这样描述，当一个数筛去小于等于自身开方的数之后就之多只有一个质因数了，详情看程序
不妨反证一下，若有第二个，则仅仅这两个数乘起来就比x大了，所以没有第二个}
program sky;{筛选法求素数，分解质因数}
var
i,j,l,tot,x:longint;
xx:array[1..100000,1..2] of longint;
a:array[1..500000]of longint;
v:array[1..500000] of boolean;
procedure init;{打素数表，思想为从头筛，找到一个质数就把它所有倍数删去（布尔数组实现），直至没有}
begin
assign(output,'pr.out');rewrite(output);
l:=0;
for i:=2 to 500000 do{500000以内的素数}
begin
if not v[i] then
begin
inc(tot); a[tot]:=i; j:=2;
while i*j<=500000 do begin v[i*j]:=true;inc(j); end;
end;
end;
// for i:=1 to tot do writeln(a[i]);
// close(output);
end;
procedure doing;
begin
read(x);
i:=0; tot:=0;
while a[i]<sqrt(x) do{虽然x在变，不过这不会导致结果出错，因为div之后就存储起来，问题就变成弄一个更小的数的质因数，之所以不取等号是因为，先判断再运算，举个例子，当x=9时，第一个质数为2，跳过，发现没超，第二个为3，发现可以div，自己模拟吧。。。}
begin
inc(i);
if x mod a[i]=0 then begin inc(tot); xx[tot,1]:=a[i]; end;{xx数组存储读入的x的质因数，第一个域表示质因数，第二个域为该质因数的个数}
while x mod a[i]=0 do{记录个数。。}
begin
inc(xx[tot,2]); x:=x div a[i];
end;
end;
if x<>1 then begin inc(tot); xx[tot,1]:=x; xx[tot,2]:=1; end;{处理边界，x最后还有剩余的话，那么就是那个大于sqrt(x)的数}
for i:=1 to tot do writeln(xx[i,1],' ',xx[i,2]);
end;
begin
init;
doing;
close(output);
end.