#include <bits/stdc++.h>
#define PRIME 1
#define COMPOSITE 0
#define MAXNUMFACT 64
using namespace std;
typedef unsigned long long LLU;
LLU Fa[MAXNUMFACT];
int nfact = -1;
map <LLU, LLU> mp;
int miller_rabin_testing(int acc, LLU N);
void decompose(LLU p, int *k, LLU *m);
LLU llu_fsqrt(LLU N);
LLU mod_mul(LLU a, LLU b, LLU p);
LLU random64();
LLU next_prng(LLU x, LLU N);
LLU gcd(LLU a, LLU b);
LLU find_factor(LLU N);
LLU mod_power(LLU a, LLU b, LLU p);
void fast_native_fact(LLU N);
int llu_cmp(const void *a, const void *b);
void pollard_rho_fact(LLU N);
void print_factors();
int main () {
ios::sync_with_stdio(false); cin.tie(0);
LLU n;
cin >> n;
pollard_rho_fact(n);
print_factors();
return 0;
}
void pollard_rho_fact(LLU(N)){
if(N == LLU(1)) return;
else if(N < (LLU(1) << 10)) fast_native_fact(N);
else if(miller_rabin_testing(10, N) == PRIME) Fa[++nfact] = N;
else {
LLU p = (LLU)0;
while(p == 0 || p == N) p = find_factor(N);
pollard_rho_fact(p);
pollard_rho_fact(N/p);
}
}
LLU find_factor(LLU N) {
LLU x = random64()% N;
LLU y = x;
LLU p = 1;
do{
x = next_prng(x, N);
y = next_prng(next_prng(y, N), N);
if (x > y) p = gcd(x-y,N);
else p = gcd(y-x,N);
} while(p == 1);
return p;
}
LLU next_prng(LLU x, LLU N){
LLU xs = mod_mul(x,x,N);
return xs + LLU(1);
}
void fast_native_fact(LLU N){
while (N % 2 == 0){
Fa[++nfact] = LLU(2);
N = N/2;
}
while (N % 3 == 0){
Fa[++nfact] = LLU(3);
N = N/3;
}
if (N == 1) return;
if (miller_rabin_testing(10, N) == PRIME ) {
Fa[++nfact] = N;
return;
}
LLU Q = 5;
int diff = 2;
int sqrtN = llu_fsqrt(N);
while (Q <= sqrtN) {
if (N %Q == 0) {
Fa[++nfact] = Q;
N = N/Q;
sqrtN = llu_fsqrt(N);
if (miller_rabin_testing(10, N) == PRIME ) {
Fa[++nfact] = N;
return;
}
}
else {
Q = Q + LLU(diff);
diff = (diff&2) + 2;
}
}
}
void print_factors() {
for (int i = 0; i <= nfact; i++){
mp[Fa[i]]++;
}
for (auto it : mp) {
cout << it.first << " " << it.second << "\n";
}
}
int llu_cmp(const void *a, const void *b){
return *(LLU*)a - *(LLU*)b;
}
int witness(LLU a, LLU N){
LLU m;
int k;
decompose(N-1, &k, &m);
LLU B[k+1];
B[0] = mod_power(a, m, N);
if(B[0] == 1) return PRIME;
else {
int i = 1;
while(i <= k) {
B[i] = mod_mul(B[i-1], B[i-1], N);
if(B[i] == 1) {
if(B[i-1] == N-1) return PRIME;
else return COMPOSITE;
}
i++;
}
}
return COMPOSITE;
}
int miller_rabin_testing(int acc, LLU N) {
LLU a = 0;
for (int i = 0; i <= acc; i++) {
a = random64()%(N-2) + 2;
if (gcd(a,N) != 1) return COMPOSITE;
else if (mod_power(a, N-1, N) != 1) return COMPOSITE;
else if (witness(a, N) == COMPOSITE) return COMPOSITE;
}
return PRIME;
}
void decompose(LLU p, int *k, LLU *m){
int i = 0;
while ((p & 1) == 0){
i++;
p = p >> 1;
}
*k = i;
*m = p;
}
LLU mod_mul(LLU a, LLU b, LLU p){
if (b == 1) return a % p;
else {
LLU x = mod_mul(a, b>>1, p);
if ((b & 1) == 0) return (x<<1)%p;
else return (((x<<1)%p)+a)%p;
}
return 0;
}
LLU mod_power(LLU a, LLU b, LLU p){
if (b == 1) return a % p;
else {
LLU x = mod_power(a, b/2, p);
if((b & 1) == 0) return mod_mul(x, x, p);
else return (mod_mul(mod_mul(x, x, p), a, p));
}
}
LLU gcd(LLU a, LLU b){
LLU tmp;
while (b != 0){
tmp = b;
b = a % b;
a = tmp;
}
return a;
}
LLU random64() {
LLU n = 0;
int l = rand()%(RAND_MAX-2)+2;
int r = rand()%(RAND_MAX) + rand()%2;
n = n | LLU(r);
n = n << 32;
n = n | LLU(l);
return n;
}
LLU llu_fsqrt(LLU N){
LLU X, A2, R;
X = N;
A2 = LLU(1) << 62;
R = 0;
while (N < A2) A2 >>= 2;
while (A2 > 0) {
if (X >= R + A2) {
X -= R + A2;
R = (R >> 1) + A2;
A2 = A2>> 2;
}
else {
A2 = A2 >> 2;
R = R >> 1;
}
}
return R;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgUFJJTUUgMQojZGVmaW5lIENPTVBPU0lURSAwCiNkZWZpbmUgTUFYTlVNRkFDVCA2NAoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdHlwZWRlZiB1bnNpZ25lZCBsb25nIGxvbmcgTExVOwoKTExVIEZhW01BWE5VTUZBQ1RdOwppbnQgbmZhY3QgPSAtMTsKbWFwIDxMTFUsIExMVT4gbXA7CgppbnQgbWlsbGVyX3JhYmluX3Rlc3RpbmcoaW50IGFjYywgTExVIE4pOwp2b2lkIGRlY29tcG9zZShMTFUgcCwgaW50ICprLCBMTFUgKm0pOwpMTFUgbGx1X2ZzcXJ0KExMVSBOKTsKTExVIG1vZF9tdWwoTExVIGEsIExMVSBiLCBMTFUgcCk7CkxMVSByYW5kb202NCgpOwpMTFUgbmV4dF9wcm5nKExMVSB4LCBMTFUgTik7CkxMVSBnY2QoTExVIGEsIExMVSBiKTsKTExVIGZpbmRfZmFjdG9yKExMVSBOKTsKTExVIG1vZF9wb3dlcihMTFUgYSwgTExVIGIsIExMVSBwKTsKdm9pZCBmYXN0X25hdGl2ZV9mYWN0KExMVSBOKTsKaW50IGxsdV9jbXAoY29uc3Qgdm9pZCAqYSwgY29uc3Qgdm9pZCAqYik7CnZvaWQgcG9sbGFyZF9yaG9fZmFjdChMTFUgTik7CnZvaWQgcHJpbnRfZmFjdG9ycygpOwoKaW50IG1haW4gKCkgewogICAgaW9zOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOyBjaW4udGllKDApOwogICAgTExVIG47CiAgICBjaW4gPj4gbjsKCXBvbGxhcmRfcmhvX2ZhY3Qobik7CglwcmludF9mYWN0b3JzKCk7CglyZXR1cm4gMDsKfQoKdm9pZCBwb2xsYXJkX3Job19mYWN0KExMVShOKSl7CglpZihOID09IExMVSgxKSkgcmV0dXJuOwoJZWxzZSBpZihOIDwgKExMVSgxKSA8PCAxMCkpIGZhc3RfbmF0aXZlX2ZhY3QoTik7CgllbHNlIGlmKG1pbGxlcl9yYWJpbl90ZXN0aW5nKDEwLCBOKSA9PSBQUklNRSkgRmFbKytuZmFjdF0gPSBOOwoJZWxzZSB7CgkJTExVIHAgPSAoTExVKTA7CgkJd2hpbGUocCA9PSAwIHx8IHAgPT0gTikgcCA9IGZpbmRfZmFjdG9yKE4pOwoJCXBvbGxhcmRfcmhvX2ZhY3QocCk7CgkJcG9sbGFyZF9yaG9fZmFjdChOL3ApOwoJfQp9CgpMTFUgZmluZF9mYWN0b3IoTExVIE4pIHsKCUxMVSB4ID0gcmFuZG9tNjQoKSUgTjsKCUxMVSB5ID0geDsKCUxMVSBwID0gMTsKCWRvewoJCXggPSBuZXh0X3BybmcoeCwgTik7CgkJeSA9IG5leHRfcHJuZyhuZXh0X3BybmcoeSwgTiksIE4pOwoJCWlmICh4ID4geSkgcCA9IGdjZCh4LXksTik7CgkJZWxzZSBwID0gZ2NkKHkteCxOKTsKCX0gd2hpbGUocCA9PSAxKTsKCXJldHVybiBwOwp9CgpMTFUgbmV4dF9wcm5nKExMVSB4LCBMTFUgTil7CglMTFUgeHMgPSBtb2RfbXVsKHgseCxOKTsKCXJldHVybiB4cyArIExMVSgxKTsKfQoKdm9pZCBmYXN0X25hdGl2ZV9mYWN0KExMVSBOKXsKCXdoaWxlIChOICUgMiA9PSAwKXsKCQlGYVsrK25mYWN0XSA9IExMVSgyKTsKCQlOID0gTi8yOwoJfQoJd2hpbGUgKE4gJSAzID09IDApewoJCUZhWysrbmZhY3RdID0gTExVKDMpOwoJCU4gPSBOLzM7Cgl9CglpZiAoTiA9PSAxKSByZXR1cm47CglpZiAobWlsbGVyX3JhYmluX3Rlc3RpbmcoMTAsIE4pID09IFBSSU1FICkgewoJCQlGYVsrK25mYWN0XSA9IE47CgkJCXJldHVybjsKCX0KCUxMVSBRID0gNTsKCWludCBkaWZmID0gMjsKCWludCBzcXJ0TiA9IGxsdV9mc3FydChOKTsKCXdoaWxlIChRIDw9IHNxcnROKSB7CgkJaWYgKE4gJVEgPT0gMCkgewoJCQlGYVsrK25mYWN0XSA9IFE7CgkJCU4gPSBOL1E7CgkJCXNxcnROID0gbGx1X2ZzcXJ0KE4pOwoJCQlpZiAobWlsbGVyX3JhYmluX3Rlc3RpbmcoMTAsIE4pID09IFBSSU1FICkgewoJCQkJRmFbKytuZmFjdF0gPSBOOwoJCQkJcmV0dXJuOwoJCQl9CgkJfQoJCWVsc2UgewoJCQlRID0gUSArIExMVShkaWZmKTsKCQkJZGlmZiA9IChkaWZmJjIpICsgMjsKCQl9Cgl9Cn0KCnZvaWQgcHJpbnRfZmFjdG9ycygpIHsKCWZvciAoaW50IGkgPSAwOyBpIDw9IG5mYWN0OyBpKyspewoJCW1wW0ZhW2ldXSsrOwoJfQoJZm9yIChhdXRvIGl0IDogbXApIHsKICAgICAgICBjb3V0IDw8IGl0LmZpcnN0IDw8ICIgIiA8PCBpdC5zZWNvbmQgPDwgIlxuIjsKCX0KfQoKaW50IGxsdV9jbXAoY29uc3Qgdm9pZCAqYSwgY29uc3Qgdm9pZCAqYil7CglyZXR1cm4gKihMTFUqKWEgLSAqKExMVSopYjsKfQoKaW50IHdpdG5lc3MoTExVIGEsICBMTFUgTil7CiAgICBMTFUgbTsKCWludCBrOwoJZGVjb21wb3NlKE4tMSwgJmssICZtKTsKCUxMVSBCW2srMV07CglCWzBdID0gbW9kX3Bvd2VyKGEsIG0sIE4pOwoJaWYoQlswXSA9PSAxKSByZXR1cm4gUFJJTUU7CgllbHNlIHsKCQlpbnQgaSA9IDE7CgkJd2hpbGUoaSA8PSBrKSB7CgkJCUJbaV0gPSAgbW9kX211bChCW2ktMV0sIEJbaS0xXSwgTik7CgkJCWlmKEJbaV0gPT0gMSkgewoJCQkJaWYoQltpLTFdID09IE4tMSkgcmV0dXJuIFBSSU1FOwogICAgICAgICAgICAgICAgZWxzZSByZXR1cm4gQ09NUE9TSVRFOwoJCQl9CgkJCWkrKzsKCQl9Cgl9CglyZXR1cm4gQ09NUE9TSVRFOwp9CgppbnQgbWlsbGVyX3JhYmluX3Rlc3RpbmcoaW50IGFjYywgTExVIE4pIHsKCUxMVSBhID0gMDsKCWZvciAoaW50IGkgPSAwOyBpIDw9IGFjYzsgaSsrKSB7CgkJYSA9IHJhbmRvbTY0KCklKE4tMikgKyAyOwoJCWlmIChnY2QoYSxOKSAhPSAxKSByZXR1cm4gQ09NUE9TSVRFOwoJCWVsc2UgaWYgKG1vZF9wb3dlcihhLCBOLTEsIE4pICE9IDEpIHJldHVybiBDT01QT1NJVEU7CgkJZWxzZSBpZiAod2l0bmVzcyhhLCBOKSA9PSBDT01QT1NJVEUpIHJldHVybiBDT01QT1NJVEU7Cgl9CglyZXR1cm4gUFJJTUU7Cn0KCnZvaWQgZGVjb21wb3NlKExMVSBwLCBpbnQgKmssIExMVSAqbSl7CglpbnQgaSA9IDA7Cgl3aGlsZSAoKHAgJiAxKSA9PSAwKXsKCQlpKys7CgkJcCA9IHAgPj4gMTsKCX0KCSprID0gaTsKCSptID0gcDsKfQoKTExVIG1vZF9tdWwoTExVIGEsIExMVSBiLCBMTFUgcCl7CglpZiAoYiA9PSAxKSByZXR1cm4gYSAlIHA7CgllbHNlIHsKCQlMTFUgeCA9IG1vZF9tdWwoYSwgYj4+MSwgcCk7CgkJaWYgKChiICYgMSkgPT0gMCkgcmV0dXJuICh4PDwxKSVwOwoJCWVsc2UgcmV0dXJuICgoKHg8PDEpJXApK2EpJXA7Cgl9CglyZXR1cm4gMDsKfQoKTExVIG1vZF9wb3dlcihMTFUgYSwgTExVIGIsIExMVSBwKXsKCWlmIChiID09IDEpIHJldHVybiBhICUgcDsKCWVsc2UgewoJCUxMVSB4ID0gbW9kX3Bvd2VyKGEsIGIvMiwgcCk7CgkJaWYoKGIgJiAxKSA9PSAwKSByZXR1cm4gbW9kX211bCh4LCB4LCBwKTsKCQllbHNlIHJldHVybiAobW9kX211bChtb2RfbXVsKHgsIHgsIHApLCBhLCBwKSk7Cgl9Cn0KCkxMVSBnY2QoTExVIGEsIExMVSBiKXsKCUxMVSB0bXA7Cgl3aGlsZSAgKGIgIT0gMCl7CgkJdG1wID0gYjsKCQliID0gYSAlIGI7CgkJYSA9IHRtcDsKCX0KCXJldHVybiBhOwp9CgpMTFUgcmFuZG9tNjQoKSB7CglMTFUgbiAgPSAwOwoJaW50IGwgPSByYW5kKCklKFJBTkRfTUFYLTIpKzI7CglpbnQgciA9IHJhbmQoKSUoUkFORF9NQVgpICsgcmFuZCgpJTI7CgluID0gbiB8IExMVShyKTsKCW4gPSBuIDw8IDMyOwoJbiA9IG4gfCBMTFUobCk7CglyZXR1cm4gbjsKfQoKTExVIGxsdV9mc3FydChMTFUgIE4pewoJTExVIFgsIEEyLCBSOwoJWCA9IE47CglBMiA9IExMVSgxKSA8PCA2MjsKCVIgPSAwOwoJd2hpbGUgKE4gPCBBMikgQTIgPj49IDI7Cgl3aGlsZSAoQTIgPiAwKSB7CgkJaWYgKFggPj0gUiArIEEyKSB7CgkJCVggLT0gUiArIEEyOwoJCQlSID0gKFIgPj4gMSkgKyBBMjsKCQkJQTIgPSBBMj4+IDI7CgkJfQoJCWVsc2UgewoJCQlBMiA9IEEyID4+IDI7CgkJCVIgPSBSID4+IDE7CgkJfQoJfQoJcmV0dXJuIFI7Cn0=